小 T 和她的朋友小 U 在看天文台看星星。
天上有
颗星星，第
颗星星的亮度为
。现在小 T 想把这些星星分组。
具体地，她每次可以选取若干颗还未分组的星星（任意选取，不需要连续），如果它们满足：
记一共选取了
颗星星，它们的亮度分别是
；
；
%20%2B%20(c_1%20%5Coplus%20c_2%20%5Coplus%20%5Ccdots%20%5Coplus%20c_m)%20%3D%202%20%5Ctimes%20%5Cmin(c_1%2Cc_2%2C%5Ccdots%2Cc_m))
；
那么小 T 就可以将这些星星分为一组。
小 T 想要让每颗星星都被分到某一组里，请问她最少需要分多少组？
本题有多组数据，你需要对每组数据都求出对应的结果。
在本题中，
指最小数，例如
%3D4)
；
指最小公倍数，例如
%3D12)
；
表示按位异或运算。
如果您需要更多最小公倍数相关的知识，请参考
OI-Wiki：最小公倍数 ；如果您需要更多位运算相关的知识，请参考
OI-Wiki：与、或、异或 。
输入描述:
每个测试文件均包含多组测试数据。第一行输入一个整数
)
代表数据组数，每组测试数据描述如下：
第一行输入一个整数
)
代表星星的数量。
第二行输入
个整数
)
代表每颗星星的亮度。
除此之外，保证单个测试文件的
之和不超过
。
输出描述:
对于每一组数据，在单独的一行上输出一个整数，代表最少需要分出的组数。