CF1926D Vlad and Division

Vladislav 有 $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) \ne y_2(i)$。 Vlad 需要的最小分组数是多少？每个数必须恰好属于一个组。

第一行包含一个整数 $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 < 2^{31}$）。 所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

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

在第一个测试用例中，任意两个数的最后 $31$ 位都相同，因此需要将每个数单独分组。 在第二个测试用例中，$a_1=0000000000000000000000000000000_2$，$a_2=1111111111111111111111111111111_2$，它们可以放在同一组，因为对于每个 $1 \leq i \leq 31$，都有 $a_1(i) \ne a_2(i)$。 由 ChatGPT 4.1 翻译