平方数
提交数: 70, 通过率: 10%, 平均分: 10
题目描述:
给出n个整数，从中选出1个或多个，使得选出的整数的乘积是完全平方数。问一共有多少种选法。
输入格式:
输入第一行为一个整数t，即测试数据的数量。
每组数据包含两行，第一行为整数n，第二行包含n个整数。
输出格式:
对于每组数据，输出方案总数。
答案对109 + 7取模。
样例输入:
1 4 4 6 10 15
样例输出:
3
提示:
对于100%的数据，1 ≤ t ≤ 30，1 ≤ n ≤ 100，所有整数均不小于1，不大于1015，且不含大于500的素因子。
空间限制: 256MB