311246: CF1955F. Unfair Game

F. Unfair Gametime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

Alice and Bob gathered in the evening to play an exciting game on a sequence of $n$ integers, each integer of the sequence doesn't exceed $4$. The rules of the game are too complex to describe, so let's just describe the winning condition — Alice wins if the bitwise XOR of all the numbers in the sequence is non-zero; otherwise, Bob wins.

The guys invited Eve to act as a judge. Initially, Alice and Bob play with $n$ numbers. After one game, Eve removes one of the numbers from the sequence, then Alice and Bob play with $n-1$ numbers. Eve removes one number again, after which Alice and Bob play with $n - 2$ numbers. This continues until the sequence of numbers is empty.

Eve seems to think that in such a game, Alice almost always wins, so she wants Bob to win as many times as possible. Determine the maximum number of times Bob can win against Alice if Eve removes the numbers optimally.

Input

The first line contains an integer $t$ ($1 \le t \le 10^4$) — the number of test cases.

The first and only line of each test case contains four integers $p_i$ ($0 \le p_i \le 200$) — the number of ones, twos, threes, and fours in the sequence at the beginning of the game.

Output

For each test case, print the maximum number of times Bob will win in a separate line, if Eve removes the numbers optimally.

ExampleInput

5
1 1 1 0
1 0 1 2
2 2 2 0
3 3 2 0
0 9 9 9

Output

1
1
3
3
12

Note

In the first example, Bob wins when Eve has not removed any numbers yet.

In the second example, Bob wins if Eve removes one one and one three.

题目大意：
爱丽丝和鲍勃玩一个关于数列的游戏，数列由n个整数组成，每个整数都不超过4。游戏规则复杂，但赢的条件很简单：如果数列中所有数的按位异或（bitwise XOR）结果非零，则爱丽丝赢；否则，鲍勃赢。裁判伊芙会依次从数列中移除一个数，直到数列清空，每移除一个数，爱丽丝和鲍勃就按新的数列玩一次游戏。求如果伊芙最优地移除数，鲍勃最多能赢多少次。

输入输出数据格式：
输入：
- 第一行包含一个整数t（1≤t≤10^4），表示测试用例的数量。
- 每个测试用例包含一行，有四个整数p_i（0≤p_i≤200），分别表示数列中1、2、3、4的数量。

输出：
- 对于每个测试用例，输出一行，表示伊芙最优移除数的情况下，鲍勃最多能赢多少次。

示例：
输入：
```
5
1 1 1 0
1 0 1 2
2 2 2 0
3 3 2 0
0 9 9 9
```
输出：
```
1
1
3
3
12
```

注意：
- 在第一个例子中，鲍勃在伊芙移除任何数字之前就赢了。
- 在第二个例子中，如果伊芙移除一个1和一个3，鲍勃就会赢。题目大意： 爱丽丝和鲍勃玩一个关于数列的游戏，数列由n个整数组成，每个整数都不超过4。游戏规则复杂，但赢的条件很简单：如果数列中所有数的按位异或（bitwise XOR）结果非零，则爱丽丝赢；否则，鲍勃赢。裁判伊芙会依次从数列中移除一个数，直到数列清空，每移除一个数，爱丽丝和鲍勃就按新的数列玩一次游戏。求如果伊芙最优地移除数，鲍勃最多能赢多少次。 输入输出数据格式： 输入： - 第一行包含一个整数t（1≤t≤10^4），表示测试用例的数量。 - 每个测试用例包含一行，有四个整数p_i（0≤p_i≤200），分别表示数列中1、2、3、4的数量。 输出： - 对于每个测试用例，输出一行，表示伊芙最优移除数的情况下，鲍勃最多能赢多少次。 示例： 输入： ``` 5 1 1 1 0 1 0 1 2 2 2 2 0 3 3 2 0 0 9 9 9 ``` 输出： ``` 1 1 3 3 12 ``` 注意： - 在第一个例子中，鲍勃在伊芙移除任何数字之前就赢了。 - 在第二个例子中，如果伊芙移除一个1和一个3，鲍勃就会赢。