我们可以把一次操作理解为:
选择数组中的两个数 x,y,向数组末尾加入 x&y。
由于新加入的数还可以继续参与操作,所以最终能够得到的数,本质上就是原数组中若干个数的按位与结果。
也就是说,最终可能出现的数一定形如:
小红有一个数组 a,初始长度为n。
她可以进行如下操作任意次(次数不限):
选择两个下标 (i,j (1≤i,j≤m)(其中 m 为当前数组长度),计算 (v=ai&aj)((&) 表示按位与),并将v 追加到数组末尾,使数组长度加1。
在进行了任意次操作后,数组中可能出现很多元素。我们关心数组中不同元素的个数。
请你计算:通过任意次操作后,数组中最多能出现多少个不同的元素。
符号 & 表示按位与运算(对两个数的二进制逐位与),对应位均为 1时结果位为 1,否则为 0。
每个测试文件均包含多组测试数据。
第一行输入一个整数 (T (1≤T≤104) 表示数据组数,每组测试数据描述如下:
除此之外,保证单个测试文件中所有测试数据的 n 之和不超过 2×105
对于每组测试数据,新起一行输出一个整数,表示最多能出现的不同元素个数。
输入
2
3
7 3 5
4
1 2 4 8
输出
4
5