题目描述

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$。

输出格式

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

样例

9
4
1 4 3 4
2
0 2147483647
5
476319172 261956880 2136179468 1671164475 1885526767
3
1335890506 811593141 1128223362
4
688873446 627404104 1520079543 1458610201
4
61545621 2085938026 1269342732 1430258575
4
0 0 2147483647 2147483647
3
0 0 2147483647
8
1858058912 289424735 1858058912 2024818580 1858058912 289424735 122665067 289424735

4
1
3
2
2
3
2
2
4

样例说明

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

在第二个测试用例中，$a_1=0000000000000000000000000000000_2$，$a_2=1111111111111111111111111111111_2$，它们可以放在同一组，因为对于每个 $1 \leq i \leq 31$，都有 $a_1(i) \ne a_2(i)$。

由 ChatGPT 4.1 翻译

来源

Codeforces 1926D，英文题名 Vlad and Division。