
ZOJ Problem Set  4057
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. InputThere 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$. OutputFor each test case, output an integer denoting the maximum size of $S$. Sample Input3 3 1 2 3 3 1 1 1 5 1 2323 534 534 5 Sample Output2 3 2 Author: LIN, Xi Source: The 2018 ACMICPC Asia Qingdao Regional Contest, Online 