题目描述

给定$n$个整数$a_i$，要求从中取出至少一个整数，使取出的数的乘积为完全平方数，问有多少种取法。

数据保证，$a_i$的质因子均不大于$500$。

输入格式

第一行输入一个整数$n$。 第二行输入$n$个整数$a_i$。

输出格式

输出一行一个整数，表示你的答案，由于这个数可能很大，你只需要输出在模$2^{64}$下的结果即可。

样例输入 #1

4
4 6 10 15

样例输出 #1

3

说明/提示

有$1\leq n\leq 100,1\leq a_i\leq 10^{15}$，且$a_i$的质因子均不超过$500$。