不公平游戏

时间限制：2s
空间限制：256MB

题目描述

Alice 和 Bob 使用一个整数序列进行游戏，序列中的每个数都属于 $\{1,2,3,4\}$。在一局游戏中，如果序列中所有数的按位异或结果不为 $0$，Alice 获胜；否则 Bob 获胜。

初始序列中共有 $p_1$ 个 $1$、$p_2$ 个 $2$、$p_3$ 个 $3$ 和 $p_4$ 个 $4$。如果序列非空，Alice 和 Bob 就用当前序列进行一局游戏；每局结束时，Eve 会从序列中移除一个数。这个过程持续到序列为空。

Eve 希望 Bob 获胜的局数尽可能多。假设 Eve 每次都采用最优策略，求 Bob 最多能获胜多少局。

输入格式

第一行包含一个整数 $t$，表示测试用例数量。

接下来 $t$ 行，每行包含四个整数 $p_1,p_2,p_3,p_4$，依次表示初始序列中 $1,2,3,4$ 的数量。

输出格式

对于每个测试用例，输出一行一个整数，表示 Eve 最优操作时 Bob 最多能获胜的局数。

样例输入 1

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

样例输出 1

1
1
3
3
12

数据范围

• 对于所有数据，满足 $1 \le t \le 10^4$。
• 对于所有数据，满足 $0 \le p_i \le 200\quad(1\le i\le 4)$。