Penny has started taking mathematics classes and has got better at it. She now wants to challenge Sheldon at this expertise and make a fool out of him. She writes down a list of numbers as list A and calculates the median of it. Then she calculates the absolute deviation of each number from this median value to make list B. Now she finds the median of this list B. She asks Sheldon to find the minimum number of elements he needs to change in list A so that the median of list B becomes equal to 0. Can you help Sheldon do this?

For example:

• List of numbers (A):  4 5 3 1 2
• Median of list A = 3
• List of Absolute Deviation from median (B) = 1 2 0 2 1
• Median of list B = 1

Note: Median of even length list is the mean of 2 middle values.

Constraints

0 < T ≤ 10
0 < N ≤ 10⁵
0 ≤ A[i] ≤ 10⁹

Input

T Number of test cases followed 2T lines.
First line of test case contains N, size of array.
Second line contains A[0] to A[N-1]  the numbers of the array.

Output

T lines each containing a single number which denotes the minimum number of elements we need to change to get the median of the absolute deviation of numbers from median to be 0.

Example

Input:
2
5
4 5 3 1 2
10
5 5 5 254 5 5 768 5 5 5

Output:
2
0