徐老师的完全平方数

文件读写

• 输入文件square.in
• 输出文件square.out

限制

• 2000ms
• 512MB

题目描述

徐老师有 $n$ 个整数，分别为 $a_1,a_2,a_3 \sim a_n$

现在徐老师想从中选出任意个数字（至少一个），将它们相乘

徐老师想知道有多少种不同的选数方案，可以使得最终的乘积为完全平方数？

输入格式

输入一行，包含一个整数 $T$，表示测试数据个数

对于每组测试数据:

输入第一行包含一个整数 $n$ 表示数字个数

输入第二行包含 $n$ 个整数，分别表示每个数字 $a_i$

输出格式

对于每组测试数据输出一个结果，表示答案，由于答案可能很大，请你将答案对 $10^9+7$ 取模

数据范围

样例输入

3
3
3 3 8
4
2 4 8 16
3
3 3 3

样例输出

1
7
3

样例解释

对于第一组测试数据，只有选 $3,3$ 可以得到完全平方数

对于第二组测试数据，有以下 7 种方案：$4,16,2 * 8,4 * 16,2 * 4 * 8,2 * 8 * 16,2 * 4 * 8 * 16$