L. Puzzle
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output
$$$2\times 2$$$ and $$$3\times 3$$$ rectangle examples, A, B, C, D represent four basic blocks

Little Y wants to play a type of puzzle that consists of four basic blocks, as shown in the image above. Little Y has $$$A, B, C, D$$$ of these four types of blocks. Now he wants to use as many blocks as possible to form a rectangle (either a rectangle or a square). The question is, what is the maximum number of blocks he can use?

The formed rectangle must satisfy the following conditions:

  1. Any two adjacent basic blocks must form a concave and convex structure;
  2. The four edges of the formed rectangle must not have any protrusions or indentations;
  3. Unlike common puzzle games, the blocks in this game do not have patterns, and blocks of the same type are considered identical.
Input

The first line contains a positive integer $$$T$$$ $$$(1 \leq T \leq 10^4)$$$, indicating the number of test cases.

For each test case, each line contains four integers $$$A, B, C, D$$$ $$$(0 \leq A, B, C, D \leq 10^3)$$$, representing the number of four types of basic blocks.

Output

Output $$$n$$$ lines, each line containing an integer that indicates the maximum number of given blocks that can be used to form a rectangle. If it is not possible to form a rectangle, please output $$$0$$$.

Example
Input
2
4 0 0 0
4 4 4 4
Output
4
16