← 返回题目列表

Codeforces · 1955/F

F. 不公平的游戏

中文机器翻译题面 查看原题

Alice 和 Bob 晚上聚集在一起,在 $$$n$$$ 个整数序列上玩了一场激动人心的游戏,序列中的每个整数不超过 $$$4$$$。游戏规则太复杂,无法描述,所以我们只描述获胜条件:如果序列中所有数字的按位异或不为零,则爱丽丝获胜;否则,鲍勃获胜。

这些人邀请伊芙担任评委。最初,爱丽丝和鲍勃玩 $$$n$$$ 数字。一场游戏结束后,Eve 从序列中删除一个数字,然后 Alice 和 Bob 玩 $$$n-1$$$ 数字。 Eve 再次删除一个数字,之后 Alice 和 Bob 玩 $$$n - 2$$$ 数字。这一直持续到数字序列为空为止。

Eve 似乎认为在这样的游戏中,Alice 几乎总是赢,所以她希望 Bob 赢的次数尽可能多。如果夏娃以最佳方式删除数字,则确定鲍勃可以战胜爱丽丝的最大次数。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。

每个测试用例的第一行也是唯一一行包含四个整数 $$$p_i$$$ ($$$0 \le p_i \le 200$$$) - 游戏开始时序列中的一、二、三和四的数量。

输出

对于每个测试用例,如果 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

注意

在第一个示例中,当 Eve 尚未删除任何数字时,Bob 获胜。

在第二个示例中,如果 Eve 删除一一和一三,则鲍勃获胜。