题目描述

农夫 John 有一台割草机，最开始是关闭的。他还有 $n$ 块田地，第 $i$ 块田地上有 $a_i$ 朵蒲公英。他将以任意顺序访问所有田地，每块田地恰好访问一次。

John 的割草机似乎有自己的想法。在访问每一块田地之前，割草机会检查该田地上的蒲公英数量是奇数还是偶数。如果是奇数，割草机会切换自身状态（如果当前关闭，则打开；如果当前打开，则关闭）。随后，如果割草机处于开启状态，他会割掉该田地上的所有蒲公英。否则，如果割草机关着，John 只是单纯访问田地，不会割掉任何蒲公英。

如果 John 以最优顺序访问这 $n$ 块田地，他最多可以割掉多少朵蒲公英？

输入格式

第一行输入一个整数 $t$（$1 \leq t \leq 10^4$），表示测试用例的数量。

对于每个测试用例，第一行输入一个整数 $n$（$1 \leq n \leq 2 \times 10^5$），表示田地数量。

接下来一行输入 $n$ 个用空格分隔的整数 $a_1, a_2, \ldots, a_n$（$1 \leq a_i \leq 10^9$），表示每块田地的蒲公英数。

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

输出格式

对于每个测试用例，输出一行，一个整数，表示在最优访问顺序下 John 最多可以割掉的蒲公英数量。

说明/提示

对于第一个测试用例，由于所有田地的蒲公英数都是偶数，John 永远无法启动割草机。割草机始终关闭，因此无法割掉任何蒲公英，答案为 $0$。

对于第二个测试用例，John 可以先访问第三块田地，此时割草机会开启。之后无论访问顺序如何，割草机始终处于开启状态，所以所有田地上的蒲公英都可以被割掉。

对于第三个测试用例，John 可以按如下顺序访问田地：第 $2$ 块、第 $1$ 块、第 $3$ 块，然后第 $4$ 块。

由 ChatGPT 5 翻译

样例

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

0
13
2999999999