题目描述

给定一个包含 $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$ 个元素都是奇数，因此无需任何操作。

对于第三组数据，一种操作次数最少的方案如下表所示。

对于第四组数据，一种操作次数最少的方案如下表所示。

说明/提示

对于所有数据：

• $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。

样例

7
5
1 3 5 7 9
4
4 4 4 4
3
2 3 4
4
3 2 2 8
6
4 3 6 1 2 1
6
3 6 1 2 1 2
5
999999996 999999997 999999998 999999999 1000000000

0
0
2
4
3
3
3