时间限制：1秒　　内存限制：256M

---

【题目描述】

　　给出 \(n\) 个整数，从中选出 1 个或多个，使得选出的整数的乘积是完全平方数。一共有多少种选法？

　　比如 {4,6,10,15} 有 3 种选法：{4}、{6,10,15} 和 {4,6,10,15}。

【输入格式】

　　输入第一行为一个整数 \(T\)，即测试数据的数量。　　
　　每组数据包含两行，第一行为整数，第二行包含 \(n\) 个整数。所有整数均不小于 1，不大于\(10^{15}\)。并且不含大于 500 的素因子。

【输出格式】

　　对于每组数据，输出方案总数，输入保证总数不超过带符号 64 位整数范围。

【输入输出样例】

　Input

4
3
2 3 5
3
6 10 15
4
4 6 10 15
3
2 2 2

　Output

0
1
3
3

【数据限制】

　　对于 \(30\%\) 的数据，\(1 ≤ n ≤20\)
　　对于 \(100\%\) 的数据，\(1 ≤ T ≤ 30\)，\(1 ≤ n ≤ 100\)

【来源】

　　Mr.he**