E. Phantoms of the XOR Tree
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

You are given an array $$$A$$$ of length $$$n$$$ consisting of distinct non-negative integers.

Consider a complete undirected graph $$$G$$$ with $$$n$$$ vertices. The weight of an edge between vertices $$$i$$$ and $$$j$$$ ($$$1 \le i \lt j \le n$$$) is defined as $$$A_i \oplus A_j$$$, where $$$\oplus$$$ denotes the bitwise XOR operation.

Since there can be multiple Minimum Spanning Trees (MST) in graph $$$G$$$, we define a new graph $$$G_{MST}$$$ which contains all the vertices of $$$G$$$, and its edge set consists of all edges that belong to at least one Minimum Spanning Tree of $$$G$$$.

Calculate and print the total number of edges in $$$G_{MST}$$$.

Input

The first line of the input contains a single integer $$$T$$$ ($$$1 \le T \le 10^4$$$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the length of the array.

The second line of each test case contains $$$n$$$ distinct integers $$$A_1, A_2, \dots, A_n$$$ ($$$0 \le A_i \lt 2^{30}$$$) — the elements of the array.

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

Output

For each test case, print a single integer on a new line — the total number of edges in the graph $$$G_{MST}$$$.

Example
Input
4
1
0
2
1 2
4
0 1 2 3
6
0 2 5 7 8 10
Output
0
1
4
7