Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 4057
XOR Clique

Time Limit: 1 Second      Memory Limit: 65536 KB

BaoBao has a sequence $a_1,a_2,\dots,a_n$. He would like to find a subset $S$ of $\{1, 2, \dots, n\}$ such that $\forall i, j \in S$, $a_i \oplus a_j < \min(a_i,a_j)$ and $|S|$ is maximum, where $\oplus$ means bitwise exclusive or.

Input

There are multiple test cases. The first line of input contains an integer $T$, indicating the number of test cases. For each test case:

The first line contains an integer $n$ ($1 \le n \le 10^5$), indicating the length of the sequence.

The second line contains n integers: $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$), indicating the sequence.

It is guaranteed that the sum of $n$ in all cases does not exceed $10^5$.

Output

For each test case, output an integer denoting the maximum size of $S$.

Sample Input

3
3
1 2 3
3
1 1 1
5
1 2323 534 534 5

Sample Output

2
3
2

Author: LIN, Xi
Source: The 2018 ACM-ICPC Asia Qingdao Regional Contest, Online
Submit    Status