J. Elias-utiful Array
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Elias is known for his love of standard problems. He achieves top rank in competitions of standard well-known problems. Moreover, he can only come up with standard problems. Here is his standard problem for this competition.

We define an array $$$B$$$ of $$$M$$$ integers to be called an Elias-utiful Array if it holds that for every pair of indices $$$(i, j)$$$ such that $$$(1 \le i \lt j \le N)$$$:

  • $$$B_i \& B_j \ge B_i \oplus B_j$$$

You're given an array $$$A$$$ of size $$$N$$$, you need to find the maximum possible length of some subset $$$S$$$ of $$$A$$$ that makes an Elias-utiful Array.

An array $$$U$$$ is said to be a subset of array $$$V$$$, if $$$U$$$ can be obtained from $$$V$$$ by deletion of several (possibly zero or all) elements.

Note that:

  • & represents the bitwise AND operation. The bitwise AND is a binary operation that takes two bit patterns of equal length and performs the logical AND operation on each pair of corresponding bits. The result in each position is $$$1$$$ if both bits are $$$1$$$, otherwise the result is $$$0$$$. For example: $$$0101$$$ $$$($$$decimal $$$5)$$$ AND $$$0011$$$ $$$($$$decimal $$$3)$$$ $$$=$$$ $$$0001$$$ $$$($$$decimal $$$1)$$$.
  • $$$\oplus$$$ represents the bitwise XOR operation. The bitwise XOR is a binary operation that takes two bit patterns of equal length and performs the logical exclusive OR operation on each pair of corresponding bits. The result in each position is $$$1$$$ if both bits are different, otherwise the result is $$$0$$$. For example: $$$0101$$$ $$$($$$decimal $$$5)$$$ XOR $$$0011$$$ $$$($$$decimal $$$3)$$$ $$$=$$$ $$$0110$$$ $$$($$$decimal $$$6)$$$.
Input

The first line of input contains a single integer $$$T$$$ $$$(1 \le T \le 1000)$$$ — the number of testcases. Each testcase contains two lines.

The first line of each testcase contains a single integer $$$N$$$ $$$(1 \le N \le 10^5)$$$ — the size of the array $$$A$$$.

The second line of each testcase contains $$$N$$$ space-separated integers $$$A_1, A_2, \dots, A_N$$$ $$$(1 \le A_i \lt 2^{30})$$$ — the values of the array $$$A$$$.

It's guaranteed that the sum of $$$N$$$ over all testcases does not exceed $$$10^5$$$

Output

For each testcase print a single integer — the maximum possible length of some subset that makes an Elias-utiful Array.

Example
Input
3
6
8 6 2 7 2 5
3
1 10 100
2
8 12
Output
3
1
2
Note

In the first testcase, the subset that has the maximum length is $$$\{6, 7, 5\}$$$.