题目内容

给定一组初始的“数字标记”，每个标记是一个 $10$ 位二进制数，取值范围在 $0$ 到 $1023$ 之间。 你可以进行任意次操作：从当前已有的标记中任选两个（可以相同），计算它们的“逻辑与”结果——对于每一位，仅当两个标记在该位都是 $1$ 时，结果位才是 $1$，否则为 $0$。将得到的新标记加入当前集合。新标记可以继续参与后续操作。 问：通过任意次操作，最终集合中最多能包含多少个互不相同的标记？

约束条件：

• 测试用例组数 $T$ 满足 $1 \le T \le 10^4$。
• 每组数据中，初始标记个数 $n$ 满足 $1 \le n \le 2 \times 10^5$。
• 所有测试用例的 $n$ 总和不超过 $2 \times 10^5$。
• 每个初始标记的数值在 $0$ 到 $1023$ 之间。

输入描述

第一行包含一个整数 $T$，表示测试用例的组数。 接下来依次描述每组测试数据。每组数据占两行： 第一行包含一个整数 $n$，表示初始标记的个数。 第二行包含 $n$ 个整数，表示初始标记的数值。 数据保证满足题面给出的范围约束。

输出描述

对于每组测试数据，输出一行一个整数，表示通过操作最终能获得的不同标记的最大数量。

样例1

输入

1
1
5

输出

1

说明

初始只有一个标记 5（二进制 $101_2$）。任何操作 $5 \& 5$ 的结果仍然是 5，无法生成新的标记。因此最终集合中不同标记的数量为 1。

样例2

输入

1
2
3 5

输出

3

说明

初始有两个标记：3（$011_2$）和 5（$101_2$）。 计算 $3 \& 5$ 得到 1（$001_2$），这是一个之前没有的新标记。 至此集合包含 1、3、5。无论再对哪些标记进行按位与操作（例如 $1 \& 3 = 1$，$1 \& 5 = 1$，$3 \& 3 = 3$），都只能得到这三个数之一。因此最终不同标记的数量为 3。

样例3

输入

1
10
1 2 4 8 16 32 64 128 256 512

输出

11

说明

初始包含全部 $10$ 个 $2$ 的幂：$1,2,4,8,\dots,512$（每个数的二进制表示中恰有一位为 $1$）。 任意两个不同的 $2$ 的幂进行按位与，结果均为 0（例如 $1 \& 2 = 0$），生成了新标记 0。 在包含 0 之后，由于 $0 \& x = 0$，不会再产生其他数字。最终集合由原来的 $10$ 个幂和新增的 0 组成，不同标记总数为 11。

样例4

输入

1
4
7 5 3 1

输出

4

说明

初始有 7（$0111_2$）、5（$0101_2$）、3（$0011_2$）和 1（$0001_2$）。 这四个数字的最低二进制位都是 1，因此任意子集的按位与结果最低位也必定是 1，不可能得到 0。 实际计算两两按位与：$7 \& 5 = 5$，$7 \& 3 = 3$，$7 \& 1 = 1$，$5 \& 3 = 1$ 等等，得到的全部是已有的数字，没有生成任何新标记。所以最终集合的大小仍为 4。