在形状银河系中，所有的形状都是有知觉的生物，目前圆形和正方形之间存在着一场争斗。圆形希望所有的路径都是平坦的，而正方形则认为路径应该是均匀间隔的倒悬链线形状的凸起。由于这场争斗，圆形开始厌恶所有“平方偏向”的数字。如果一个数字 $s$ 能被某个整数 $x > 1$ 的平方 $x^2$ 整除，则称该数字是平方偏向的。
圆先生将这场争斗铭记在心。他接到了一项任务，即计算数组中所有数字对的最大公约数。他想更进一步，统计其中不是平方偏向的最大公约数的数量。
输入格式
第一行包含一个整数 $n$ ($1 \le n \le 10^5$)，表示数组的长度。 接下来的 $n$ 行包含整数 $a_i$ ($1 \le a_i \le 10^{12}$)，即数组中的数字。
输出格式
输出一个整数，表示满足 $\gcd(a_i, a_j)$ 不是平方偏向的数对 $(i, j)$ ($1 \le i < j \le n$) 的数量。
样例
样例输入 1
6 3 4 6 12 4 1
样例输出 1
12