2. 乘积是平方数

【题目描述】

给出 $n$ 个整数，那么它们组成的集合有 $2^n-1$ 个子集。请你计算其中有多少个子集，其中的所有元素之积是完全平方数。例如，集合 ${4,6,10,15}$ 有三个这样的子集：${4},{6,10,15}$ 和 ${4,6,10,15}$。完全平方数是指平方根为整数的数。例如：$1,4,9,16,...$

【输入格式】

输入包含多组数据。

输入文件的第 $1$ 行是一个整数 $T(1 \leq T \leq 30)$，表示测试数据组数。

接下来是 $T$ 组测试数据，每组占 $2$ 行：

第 $1$ 行是一个整数 $n(1 \leq n \leq 100)$。

第 $2$ 行是 $n$ 个正整数，由空格分隔。这些正整数在区间 $[1,10^{15}]$ 内。它们都不含超过 $500$ 的素因子。

【输出格式】

对每组测试数据，输出一行：所有元素乘积为完全平方数的子集个数。

【样例输入】

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

【样例输出】

0
1
3
3 

【来源】

UVa 11542 Square

刘汝佳，《算法竞赛入门经典训练指南》表2-12

Problemsetter: Abdullah al Mahmud

Special Thanks to: Manzurur Rahman Khan