奇偶与求和

时间限制：1 秒
空间限制：256 MB

给定一个由 $n$ 个正整数组成的数组 $a$。

在一次操作中，你可以选择任意一对下标 $(i, j)$，满足 $a_i$ 和 $a_j$ 的奇偶性不同，然后将其中较小的那个数替换为它们的和。更形式化地：

• 若 $a_i < a_j$，将 $a_i$ 替换为 $a_i + a_j$；
• 否则，将 $a_j$ 替换为 $a_i + a_j$。

求使得数组中所有元素奇偶性相同所需的最少操作次数。

输入格式

第一行包含一个整数 $t$（$1 \le t \le 10^4$）—— 测试数据组数。

每组测试数据的第一行包含一个整数 $n$（$1 \le n \le 2 \cdot 10^5$）。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 10^9$）—— 数组 $a$ 的元素。

保证所有测试数据的 $n$ 之和不超过 $2 \cdot 10^5$。

输出格式

对于每组测试数据，输出一个整数 —— 所需的最少操作次数。

样例输入

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

样例解释

• 第一个样例中，所有数已全是奇数，不需要操作。
• 第二个样例中，所有数已全是偶数，不需要操作。
• 第三个样例中，可进行两次操作 $(1,2)$ 和 $(1,3)$，数组变化：$[2,3,4] \to [5,3,4] \to [5,3,9]$。
• 第四个样例中，一种最优操作序列为 $(1,2)$、$(1,3)$、$(1,4)$、$(1,4)$，数组变化：$[3,2,2,8] \to [3,5,2,8] \to [3,5,5,8] \to [11,5,5,8] \to [11,5,5,19]$。