你搜集了 颗珍珠，第 颗珍珠的美丽度为 。现在你想把这些珍珠分组。 具体地，你每次可以选取若干颗还未分组的珍珠（任意选取，不需要编号连续），由于你已经对它们分类了很多次了，这次你决定只有当它们满足如下条件，才会分为一组：
记一共选取了 颗珍珠，它们的美丽度分别是 ；
；
你想要让每颗珍珠都被分到某一组里，但是又不想要分太多组（分组太多比较浪费盒子），那么，请问你最少需要分多少组？
在本题中， 指最小数，例如 ； 指最小公倍数，例如 ； 表示按位异或运算，例如 。
每个测试文件均包含多组测试数据。
第一行输入一个整数 代表数据组数，每组测试数据描述如下：
第一行输入一个整数 代表珍珠的数量。
第二行输入 个整数 代表每颗珍珠的美丽度。
除此之外，保证单个测试文件的 之和不超过 。
本题有多组数据，你需要对每组数据都求出对应的结果。
对于每一组数据，在单独的一行上输出一个整数，代表最少需要分出的组数。
2 2 1 2 5 1 1 4 5 1
2 3
对于第一组测试数据，如果只分一组：
，第一个条件满足；
等式左边 ；等式右边 ，第二个条件不满足。
综上，这两个数字不能分配到同一组，所以至少需要分出 组。
本题数据除了满足题目输入格式处描述的限制外，还满足：