H. Pothchola
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a directed graph with $$$n$$$ nodes numbered from $$$1$$$ to $$$n$$$. Each node $$$i$$$ has an integer value $$$a_i$$$ associated with it. For any two distinct node $$$u$$$ and $$$v$$$, there is a directed edge from $$$u$$$ to $$$v$$$ if and only if:

$$$$$$(a_u \oplus a_v \gt a_u) \quad and \quad (a_u \oplus a_v \lt a_v)$$$$$$

where $$$\oplus$$$ denotes the bitwise XOR operation.

You may start from any node and traverse the graph by following directed edges. What is the maximum number of distinct nodes that can be visited in a single path?

Input

Each test consists of several test cases. The first line contains a single integer $$$t$$$ $$$(1 \leq t \leq 10^4)$$$ — the number of test cases. The following describes the test cases:

The first line of each test case contains a single integer $$$n$$$ $$$(1 \le n \le 2 \times 10^5)$$$.

The second line of each test case contains $$$n$$$ integers $$$a_1,a_2,…,a_n$$$ $$$(0 \le a_i \le 2^{60})$$$

It is guaranteed that the sum of $$$n$$$ across all test cases does not exceed $$$2 \times 10^5$$$

Output

For each test case, output a single integer — the maximum number of distinct nodes that can be visited in a single path.

Example
Input
2
3
3 1 0
2
7 8
Output
2
1