Chef has with him an array A of length N. In one move, he can delete any element from A.

Find the minimum number of deletions Chef must make so that the following condition holds:
Let B denote the resulting array, and M be the length of B.
Then, $B_{i} \oplus B_{j}$ ≤ 1 for every 1 ≤ i, j ≤ M.

Here, $\oplus$ denotes the [bitwise XOR] operation.

For example, [3, 3, 3] and [6, 7, 6, 7] are valid final arrays, while [1, 2] and [6, 7, 8] are not (because $1 \oplus 2 = 3$ and $7\oplus 8 = 15,$ respectively).

------ Input Format ------

• The first line of input will contain a single integer T, denoting the number of test cases.
• Each test case consists of two lines of input.
• The first line of each test case contains a single integer N, denoting the length of array A.
• The second line contains $N space-separated integers A_{1}, A_{2}, \ldots, A_{N}$ — the elements of array A.

------ Output Format ------

For each test case, output on a new line the answer: the minimum number of deletions required so that the given condition is satisfied.

------ Constraints ------

$1 ≤ T ≤ 10^{5}$
$1 ≤ N ≤ 3\cdot 10^{5}$
$0 ≤ A_{i} ≤ N$
- The sum of $N$ over all test cases won't exceed $3\cdot 10^{5}$.

----- Sample Input 1 ------
4
4
2 2 2 2
5
3 4 3 4 4
5
1 2 3 4 0
6
5 5 5 6 6 6

----- Sample Output 1 ------
0
2
3
3

----- explanation 1 ------
Test case $1$: The given array already satisfies the condition, no deletions need to be done.

Test case $2$: Chef can delete both the $3$'s to make the array $[4, 4, 4]$, which satisfies the condition.

Test case $3$: Chef can use three moves as follows:
- Delete the $1$, the array is now $[2, 3, 4, 0]$.
- Delete the $4$, the array is now $[2, 3, 0]$.
- Delete the $0$, the array is now $[2, 3]$ which satisfies the condition.

It can be verified that using two or less deletions cannot give an array that satisfies the condition.

Test case $4$: Chef must either delete all the $5$'s or all the $6$'s.

见题面

见题面