Problem I: 组合平方数

Problem I: 组合平方数

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 23  Solved: 8
[Submit] [Status] [Web Board] [Creator:]

Description

现在夏天到了,学校里面越来越多的人成双成对。这让实验室众多单身的学长们很是着急。同样是九年义务教育,为什么别人就有女朋友?难道ACMer就不能拥有自己的真爱吗?就很过分。

现在学chang这有一组数字。学chang也喜欢成双成对,所以学chang就很钟爱平方数。平方数能让他心里觉得舒坦。然而现在的问题就来了,这一组数字中有多少种组合能使得乘积为一个平方数呢?真是伤脑筋。因为这个数字可能很大,所以答案要求对998244353取余。

Input

测试数据有多组,对于每组测试数据:

第一行输入一个整数n (1 <= n <= 1e5)

第二行输入n个整数a[i] (1 <= a[i] <= 70)

Output

对每组数据输出能组合成平方数的个数,答案对998244353取余。

Sample Input Copy

5
1 2 4 5 8
4
2 2 2 2

Sample Output Copy

7
7

HINT

对于第一组样例:(1),(4),(1,4),(2,8),(1,2,8),(2,4,8),(1,2,4,8)