CF1926D.Vlad and Division

普及/提高-

通过率:0%

AC君温馨提醒

该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

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

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

The second line of each test case contains nn given integers a1,,ana_1, \ldots, a_n ( 0aj<2310 \leq a_j < 2^{31} ).

The sum of nn over all test cases in a test does not exceed 21052 \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 3131 bits, so we need to place each number in its own group.

In the second test case, a1=00000000000000000000000000000002a_1=0000000000000000000000000000000_2 , a2=11111111111111111111111111111112a_2=1111111111111111111111111111111_2 so they can be placed in the same group because a1(i)a2(i)a_1(i) \ne a_2(i) for each ii between 11 and 3131 , inclusive.

输入输出样例

  • 输入#1

    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

    输出#1

    4
    1
    3
    2
    2
    3
    2
    2
    4

说明/提示

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

In the second test case, a1=00000000000000000000000000000002a_1=0000000000000000000000000000000_2 , a2=11111111111111111111111111111112a_2=1111111111111111111111111111111_2 so they can be placed in the same group because a1(i)a2(i)a_1(i) \ne a_2(i) for each ii between 11 and 3131 , inclusive.

首页