题目描述

FJ 有一台初始关闭的割草机和若干片蒲公英田。访问某片田前，若该田蒲公英数为奇数，割草机会先切换开关状态；若随后割草机为开启状态，则割掉该田所有蒲公英。FJ 可以任意安排访问顺序，求最多能割掉多少蒲公英。

输入格式

第一行包含整数 $t$。每组数据先给出 $n$，再给出 $n$ 个整数 $a_i$。

输出格式

对每组数据输出最大数量，即最多割掉的蒲公英数。

样例

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

0
13
2999999999

说明

若所有田的数量均为偶数，割草机永远无法开启，答案为 0。

数据范围

本题来自 Codeforces Round 1050 (Div. 4)，原题编号 CF2148D，英文题名 Destruction of the Dandelion Fields。