In 2077, everything became fashionable among robots, even arrays...

We will call an array of integers $$$a$$$ fashionable if $$$\min(a) + \max(a)$$$ is divisible by $$$2$$$ without a remainder, where $$$\min(a)$$$ — the value of the minimum element of the array $$$a$$$, and $$$\max(a)$$$ — the value of the maximum element of the array $$$a$$$.

You are given an array of integers $$$a_1, a_2, \ldots, a_n$$$. In one operation, you can remove any element from this array. Your task is to determine the minimum number of operations required to make the array $$$a$$$ fashionable.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^3$$$). The description of the test cases follows.

The first line of each test case contains one integer $$$n$$$ ($$$1 \leq n \leq 50$$$) — the size of the array $$$a$$$.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 50$$$) — the elements of the array $$$a$$$.

Output

For each test case, output one integer — the minimum number of operations required to make the array $$$a$$$ fashionable.

Note

In the first test case, at least one element needs to be removed since $$$\min(a)+\max(a)=2+5=7$$$, and $$$7$$$ is not divisible by $$$2$$$. If any of the elements are removed, only one element will remain. Then $$$\max(a) + \min(a)$$$ will be divisible by $$$2$$$.

In the second test case, nothing needs to be removed since $$$\min(a)+\max(a)=1+9=10$$$, and $$$10$$$ is divisible by $$$2$$$.

In the third test case, you can remove the elements with values $$$2$$$ and $$$4$$$, then $$$\min(a)+\max(a)=5+11=16$$$, and $$$16$$$ is divisible by $$$2$$$.

Fashionable Array

Examples