← 返回题目列表

Codeforces · 2148/D

D. 蒲公英田的破坏

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

农夫约翰有一台割草机,最初是关闭的。他还有 $$$n$$$ 田地,其中第 $$$i$$$ 田地有 $$$a_i$$$ 蒲公英。他会按照他想要的任何顺序访问所有字段,并且每个字段 正好一次.

FJ的割草机似乎有自己的想法。在访问田地之前,它会检查田地里的蒲公英数量是偶数还是奇数。如果它有奇数,则割草机切换其状态(如果关闭,则打开;如果打开,则关闭)。然后,如果割草机打开,它就会割掉那块地里的所有蒲公英。否则,如果割草机关闭,FJ 就会直接到田里去,不会割蒲公英。

如果FJ以最优顺序访问$$$n$$$田地,他最多能砍下多少蒲公英?

输入

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

第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) — 字段数。

以下行包含 $$$n$$$ 以空格分隔的整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) — 每个字段中蒲公英的数量。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,在新行中输出一个整数:如果 FJ 以最佳顺序访问所有 $$$n$$$ 字段,则 FJ 可以切割的最大蒲公英。

示例

输入
复制

3
3
2 4 6
4
4 2 1 6
4
1000000000 999999999 1000000000 999999999

输出
复制

0
13
2999999999

注意

对于第一个测试用例,由于不存在奇数个蒲公英的田地,FJ 永远无法打开他的割草机。由于他的割草机始终处于关闭状态,因此他永远无法切割任何蒲公英,因此答案是 $$$0$$$。

对于第二个测试用例,FJ可以先访问第三个字段;然后他的割草机就会打开。然后他可以按任意顺序访问其他字段。由于他的割草机一直开着,所以每块田里的蒲公英都可以割。

对于第三个测试用例,FJ 可以按以下顺序访问字段:字段 $$$2$$$、字段 $$$1$$$、字段 $$$3$$$、然后字段 $$$4$$$。