K. XOR Clique
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

BaoBao has a sequence a1, a2, ..., an. He would like to find a subset S of {1, 2, ..., n} such that , and |S| is maximum, where 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 ≤ n ≤ 105), indicating the length of the sequence.

The second line contains n integers: a1, a2, ..., an (1 ≤ ai ≤ 109), indicating the sequence.

It is guaranteed that the sum of n in all cases does not exceed 105.

Output

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

Example
Input
3
3
1 2 3
3
1 1 1
5
1 2323 534 534 5
Output
2
3
2