题目描述

给你一个长度为 N 的非负整数序列 $A=(A_1,\dots,A_N)$。求满足以下两个条件的整数对 $(i,j)$ 的个数：

• $1 \le i < j \le N$

• $A_i \times A_j$ 是一个平方数。

在这里，当一个非负整数 $a$ 可以用某个非负整数 $d$ 表示为 $a=d^2$ 时，这个非负整数 $a$ 就叫做一个平方数。

输入格式

按照如下格式输入：

$N$

$A_1$ $\ldots$ $A_N$

输出格式

输出一个整数，表示答案。

样例 #1

样例输入 #1

5
0 3 2 8 12

样例输出 #1

6

样例 #2

样例输入 #2

8
2 2 4 6 3 100 100 25

样例输出 #2

7

提示

• 所有输入都是整数
• $2\leq\ N\leq\ 2\times\ 10^5$
• $0\leq\ A_i\leq\ 2\times\ 10^5$