问题描述

如果 $\min(a) + \max(a)$ 能被 $2$ 整除而没有余数，我们就称一个整数数组 $a$ 为时尚数组，其中 $\min(a)$ --数组最小元素的值 $a$ ， $\max(a)$ --数组最大元素的值 $a$ 。

给你一个整数数组 $a_1, a_2, \ldots, a_n$ 。在一次操作中，你可以删除数组中的任何一个元素。你的任务是确定使数组 $a$ 时尚所需的最小操作次数。

输入格式

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$ ( $1 \le t \le 10^3$ )。测试用例说明如下。

每个测试用例的第一行包含一个整数 $n$ ( $1 \leq n \leq 50$ ) - 数组的大小 $a$ 。

每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$ ( $1 \leq a_i \leq 50$ ) - 数组 $a$ 的元素。

输出格式

对于每个测试用例，输出一个整数 - 使数组 $a$ 时尚所需的最少操作数。

样例输入

6
2
5 2
7
3 1 4 1 5 9 2
7
2 7 4 6 9 11 5
3
1 2 1
2
2 1
8
8 6 3 6 4 1 1 6

样例输出

1
0
2
1
1
3

说明

在第一个测试用例中，由于 $\min(a)+\max(a)=2+5=7$ 和 $7$ 不能被 $2$ 整除，因此至少需要删除一个元素。如果删除任何一个元素，则只剩下一个元素。那么 $\max(a) + \min(a)$ 就可以被 $2$ 整除。

在第二个测试案例中，由于 $\min(a)+\max(a)=1+9=10$ 不需要删除任何元素，而 $10$ 又能被 $2$ 整除。

在第三个测试案例中，可以删除值为 $2$ 和 $4$ 的元素，然后删除 $\min(a)+\max(a)=5+11=16$ ，并且 $16$ 可以被 $2$ 整除。