1536. 完全平方数

【题目描述】

给定 N 个数，选择一个或多个数，求使它们的乘积是完全平方数的方案总数。

【输入格式】

每个输入文件有30组询问

对于每组询问

第一行一个数 N 

第二行 N 个数

【输出格式】

每行一个数，代表每个询问的答案。

【样例输入】

4



4 6 10 15



{略去29组询问}

【样例输出】

3



{略去29个答案}

【提示】

1≤ N ≤100，每个数不大于10^15，且不含大于500的质因子