题目内容

你面前有一排能量宝石，每颗宝石都有一个正整数能量值。你可以进行任意次操作，每次操作可以从以下两种方式中选择一种：

• 丢弃任意一颗宝石，将其从序列中移除；
• 调整任意一颗宝石的能量，将其能量值增加 $1$ 或减少 $1$。

每次操作完成后，剩余宝石的总能量必须为 $2$ 的倍数（即为偶数）。你的目标是最大化操作的总次数。 请计算最多可以进行多少次操作。

数据范围：测试数据组数不超过 $10^4$，每组宝石的数量 $n$ 不超过 $2 \times 10^5$，所有测试数据中 $n$ 的总和不超过 $2 \times 10^5$；每颗宝石的初始能量 $a_i$ 是不超过 $10^9$ 的正整数。

输入描述

第一行包含一个整数 $t$ ($1 \le t \le 10^4$)，表示测试数据的组数。 接下来每组测试数据包含两行： 第一行一个整数 $n$ ($1 \le n \le 2 \times 10^5$)，表示宝石的数量； 第二行 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$)，表示每颗宝石的初始能量。 保证所有测试数据的 $n$ 之和不超过 $2 \times 10^5$。

输出描述

对于每组测试数据，输出一行一个整数，表示最多可以执行的操作次数。

样例1

输入

2
1
2
1
1

输出

1
2

说明

第一组数据：初始宝石为 [2]，总能量 $S=2$ 为偶数，偶数宝石数量 $cnt_{even}=1$。由于总能量为偶数，每次操作只能丢弃偶数宝石，因此只能进行 1 次丢弃操作。 第二组数据：初始宝石为 [1]，总能量 $S=1$ 为奇数，偶数宝石数量 $cnt_{even}=0$。公式给出答案为 $cnt_{even}+2=2$。可行操作序列：将宝石 1 调整 $+1$ 变为 2（总能量变为偶数），再丢弃这颗偶数宝石 2，共 2 次操作。

样例2

输入

1
2
1 3

输出

0

说明

宝石序列为 [1, 3]，总能量 $S=1+3=4$ 为偶数，偶数宝石数量 $cnt_{even}=0$。初始总能量为偶数，任何能量调整操作（$\pm 1$）都会使总能量变为奇数，不符合要求；丢弃操作只能丢弃偶数宝石，但当前序列中没有偶数宝石。因此无法进行任何操作，答案为 0。

样例3

输入

1
3
2 5 6

输出

4

说明

宝石序列为 [2, 5, 6]，总能量 $S=2+5+6=13$ 为奇数，偶数宝石数量 $cnt_{even}=2$（宝石 2 和 6）。根据公式答案为 $cnt_{even}+2=4$。 一种达到 4 次操作的最优策略：

1. 当前总能量为奇数，可以调整任意宝石：将奇数宝石 5 增加 1 变为 6（总能量变为 $14$，偶数）。此次操作 1 次。
2. 此时序列变为 [2, 6, 6]，全为偶数，总能量为偶数，只能依次丢弃偶数宝石：先丢弃 2（剩余 [6,6]），再丢弃一个 6（剩余 [6]），最后丢弃剩余的 6（剩余 []）。三次丢弃共 3 次操作。 总共 $1+3=4$ 次操作。最终宝石为空，无法继续操作，因此 4 是最大操作次数。