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 < 32 $ . What is the minimum number of groups Vlad needs to achieve his goal? Each number must fall into exactly one group.

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 < 2^{31} $ ). The sum of $ n $ over all test cases in a test does not exceed $ 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.