CF1993B.Parity and Sum

给定一个包含 $n$ 个整数的数组 $a$。

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

• 如果 $a_i<a_j$，那么将 $a_i$ 替换为 $a_i+a_j$。
• 否则将 $a_j$ 替换为 $a_i+a_j$。

现在需要通过若干次上述操作使得数组 $a$ 中所有元素的奇偶性相同。请你求出最少需要多少次操作。

本题包含多组数据。

第一行输入一个整数 $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。