CF1993B Parity and Sum

给定一个包含 $n$ 个整数的数组 $a$。 每次操作中，你可以选择任意一个数对 $(i,j)$，使得 $a_i$ 和 $a_j$ 奇偶性不同，即 $a_i$ 和 $a_j$ 既不同为奇数也不同为偶数。然后将 $a_i$ 和 $a_j$ 中值较小的那一个的元素的值替换为这两个元素的和，即： - 如果 $a_i

**本题包含多组数据。** 第一行输入一个整数 $T$，表示数据组数。 对于每组数据，第一行输入一个整数 $n$，表示数组 $a$ 内元素个数。第二行输入 $n$ 个整数，第 $i$ 个整数代表数组 $a$ 内的第 $i$ 个元素 $a_i$。

对于每组数据，输出仅一行，表示最少需要的操作次数。 ### 输入输出样例 见下文 _输入 #1_ 和 _输出 #1_。 ### 样例 #1 解释 对于第一组数据，显然数组 $a$ 里面的 $5$ 个元素都是奇数，因此无需任何操作。 对于第三组数据，一种操作次数最少的方案如下表所示。 | 操作次数 | 选择数对 | $a$ 数组 | | :----------: | :----------: | :----------: | | $0$ | / | $[2,3,4]$ | | $1$ | $(1,2)$ | $[\underline5,\underline3,4]$ | | $2$ | $(1,3)$ | $[\underline5,3,\underline9]$ | 对于第四组数据，一种操作次数最少的方案如下表所示。 | 操作次数 | 选择数对 | $a$ 数组 | | :----------: | :----------: | :----------: | | $0$ | / | $[3,2,2,8]$ | | $1$ | $(1,2)$ | $[\underline3,\underline5,2,8]$ | | $2$ | $(1,3)$ | $[\underline3,5,\underline5,8]$ | | $3$ | $(1,4)$ | $[\underline{11},5,5,\underline8]$ | | $4$ | $(1,4)$ | $[\underline{11},5,5,\underline{19}]$ |

对于所有数据： - $1\leqslant T\leqslant 10^4$。 - $1\leqslant n\leqslant 2\times10^5$，$\sum n\leqslant 2\times 10^5$。 - $\forall i\in[1,n],1\leqslant a_i\leqslant 10^9$。 Translated by [Eason_AC](/user/112917)。