One day, Little R saw a problem: Given a sequence $a_1 \dots a_n$, find a subsequence such that the prefix XOR values of the subsequence are strictly increasing, and maximize the length of this subsequence.
Little R thought this problem was too simple, so he strengthened it: Given a sequence $a_1 \dots a_n$, find a sequence $b$ such that every number in $b$ has appeared in $a$, and the prefix XOR values of $b$ are strictly increasing. Maximize the length of the sequence $b$. Note: The prefix XOR values of a sequence $b$ are defined as $S_i = b_1 \oplus b_2 \oplus \dots \oplus b_i$. The prefix XOR values being strictly increasing means $S_1 < S_2 < \dots < S_m$, where $m$ is the length of the sequence $b$ (where $\oplus$ denotes the XOR operation).
Input
The first line contains a positive integer $T$, representing the number of test cases. Following this are $T$ test cases. For each test case, the first line contains a positive integer $n$, representing the length of sequence $a$; the second line contains $n$ positive integers $a_1 \dots a_n$.
Output
Output $T$ lines, each representing the answer for the corresponding test case.
Examples
Input 1
2 2 1 3 3 3 11 5
Output 1
3 4
Note 1
In the first test case, taking the sequence $b$ as $1, 3, 1$, the prefix XOR values are $1, 2, 3$. In the second test case, taking the sequence $b$ as $3, 5, 11, 3$, the prefix XOR values are $3, 6, 13, 14$.
Input 2
See the provided files. Hint: In this sample, the 10 test cases satisfy the properties of subtasks 2, 3, 4, and 5 respectively.
Subtasks
| Subtask ID | $n$ | $a_i$ | Score |
|---|---|---|---|
| 1 | $\le 5$ | $\le 10$ | 10 |
| 2 | $\le 15$ | $\le 10^{18}$ | 10 |
| 3 | $\le 1000$ | $\le 1000$ | 15 |
| 4 | $\le 10^5$ | $10^{15} \le a_i \le 10^{18}$ | 15 |
| 5 | $\le 10^5$ | $\le 10^{18}$ | 50 |
For all data, $T \le 10$. Tip: The input data for this problem is large; please use a fast I/O method.