CF1926D.Vlad and Division

Vladislav has $n$ non-negative integers, and he wants to divide all of them into several groups so that in any group, any pair of numbers does not have matching bit values among bits from $1$-st to $31$-st bit (i.e., considering the $31$ least significant bits of the binary representation).

For an integer $k$, let $k_2(i)$ denote the $i$-th bit in its binary representation (from right to left, indexing from 1). For example, if $k=43$, since $43=101011_2$, then $43_2(1)=1$, $43_2(2)=1$, $43_2(3)=0$, $43_2(4)=1$, $43_2(5)=0$, $43_2(6)=1$, $43_2(7)=0$, $43_2(8)=0, \dots, 43_2(31)=0$.

Formally, for any two numbers $x$ and $y$ in the same group, the condition $x_2(i) \neq y_2(i)$ must hold for all $1 \leq i \lt 32$.

What is the minimum number of groups Vlad needs to achieve his goal? Each number must fall into exactly one group.

弗拉迪斯拉夫有 $n$ 个非负整数，他希望将所有这些数划分为若干组，使得在任意一组中，任意两个数在二进制表示的第 $1$ 位至第 $31$ 位（即最低的 $31$ 个二进制位）上均无相同的比特值。

对任意整数 $k$，记 $k_2(i)$ 表示其二进制表示中从右向左数第 $i$ 位的值（位索引从 $1$ 开始）。例如，若 $k = 43$，由于 $43 = 101011_2$，则有 $43_2(1) = 1$，$43_2(2) = 1$，$43_2(3) = 0$，$43_2(4) = 1$，$43_2(5) = 0$，$43_2(6) = 1$，$43_2(7) = 0$，$43_2(8) = 0, \dots, 43_2(31) = 0$。

形式化地说，对同一组内的任意两个数 $x$ 和 $y$，必须满足：对所有 $1 \leq i < 32$，均有 $x_2(i) \neq y_2(i)$。

为达成目标，弗拉迪斯拉夫最少需要多少个组？每个数必须且仅能属于一个组。

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

The first line of each test case contains a single integer $n$ ($1 \leq n \leq 2 \cdot 10^5$) — the total number of integers.

The second line of each test case contains $n$ given integers $a_1, \ldots, a_n$ ($0 \leq a_j \lt 2^{31}$).

The sum of $n$ over all test cases in a test does not exceed $2 \cdot 10^5$.

第一行包含一个整数 $t$（$1 \leq t \leq 10^4$）——测试用例的数量。

每个测试用例的第一行包含一个整数 $n$（$1 \leq n \leq 2 \cdot 10^5$）——整数的总个数。

每个测试用例的第二行包含 $n$ 个给定的整数 $a_1, \ldots, a_n$（$0 \leq a_j \lt 2^{31}$）。

所有测试用例中的 $n$ 之和不超过 $2 \cdot 10^5$。

For each test case, output a single integer — the minimum number of groups required to satisfy the condition.

对于每个测试用例，输出一个整数——满足条件所需的最少组数。

In the first test case, any two numbers have the same last $31$ bits, so we need to place each number in its own group.

In the second test case, $a_1=0000000000000000000000000000000_2$, $a_2=1111111111111111111111111111111_2$ so they can be placed in the same group because $a_1(i) \ne a_2(i)$ for each $i$ between $1$ and $31$, inclusive.

在第一个测试用例中，任意两个数的最低 $31$ 位都相同，因此我们需要将每个数单独分到一个组中。

在第二个测试用例中，$a_1=0000000000000000000000000000000_2$，$a_2=1111111111111111111111111111111_2$，因此它们可以被分到同一组中，因为对每个 $i$（$1 \le i \le 31$），均有 $a_1(i) \ne a_2(i)$。