D. 蒲公英田的毁灭

每次测试时间限制：$2$ 秒
每次测试内存限制：$256$ 兆字节

农夫约翰有一台割草机，起初是关闭的。
他有 $n$ 块田地，其中第 $i$ 块田地有 $a_i$ 株蒲公英。他会按自己想要的顺序访问所有田地，每块田只访问一次。

FJ 的割草机似乎有自己的意识。在参观一块田地之前，它会检查这块田地里蒲公英的数量是偶数还是奇数：

• 如果数量为奇数，割草机会切换状态（关闭时开机；开机则关闭）。
• 然后，如果割草机开着，它会割掉那块田地里的所有蒲公英（数量 $a_i$）。
• 否则，如果割草机关着，FJ 就直接去田里，不割蒲公英。

如果 FJ 以最优顺序访问 $n$ 块田地，他能够割到的最大蒲公英总数是多少？

输入

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

对于每个测试用例：

• 第一行包含一个整数 $n$（$1 \le n \le 2 \cdot 10^5$）——田地的数量。
• 下一行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 10^9$）——每块田地的蒲公英数量。

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

输出

对于每个测试用例，在新一行输出一个整数：在最优访问顺序下能割到的最大蒲公英总数。

示例

输入：

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

输出：

0
13
2999999999

注释

• 第一个测试案例：由于没有一块田地的蒲公英数量为奇数，FJ 永远无法启动割草机。因此他一直关着割草机，无法割任何蒲公英，答案为 $0$。
• 第二个测试案例：FJ 可以先访问第 $3$ 块田地（$a_3 = 1$，奇数），此时割草机会启动。然后他按任意顺序访问其他田地，由于割草机一直开着，所有田地里的蒲公英都能被割掉。总数为 $4+2+1+6 = 13$。
• 第三个测试案例：最优顺序可以是：
  第 $2$ 块（$a_2 = 999999999$，奇数，切换后割草机开，割掉它） →
  第 $1$ 块（$a_1 = 10^9$，偶数，不切换，开着则割掉） →
  第 $3$ 块（$a_3 = 10^9$，偶数，不切换，开着则割掉） →
  第 $4$ 块（$a_4 = 999999999$，奇数，切换后关闭，不割）。
  总数为 $999999999 + 10^9 + 10^9 = 2999999999$。