该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

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

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

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

输入格式

第一行输入一个整数 $t$，表示测试用例的数量。

对于每个测试用例，第一行输入一个整数 $n$，表示田地数量。

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

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

输出格式

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

样例

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

0
13
2999999999

样例解释

• 第一个测试用例：所有田地的蒲公英数都是偶数，割草机永远无法启动，因此答案为 $0$。
• 第二个测试用例：可以先访问第三块田地（蒲公英数为 $1$，奇数），此时割草机开启。之后无论访问顺序如何，割草机始终处于开启状态，所以所有田地上的蒲公英都可以被割掉，总和为 $4+2+1+6=13$。
• 第三个测试用例：按 $a_2$（奇数）、$a_1$（偶数）、$a_3$（偶数）、$a_4$（奇数）的顺序访问，可以割掉除了第一块田地外的所有蒲公英，总和为 $999999999 + 1000000000 + 999999999 = 2999999999$。

数据范围与提示

• $1 \leq t \leq 10^4$
• $1 \leq n \leq 2 \times 10^5$，所有测试用例的 $n$ 之和不超过 $2 \times 10^5$
• $1 \leq a_i \leq 10^9$