问题描述

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

• $1\leq i<j\leq N$
• $A_iA_j$ 是完全平方数。

这里，当非负整数 $a$ 可以用某个非负整数 $d$ 表示为 $a=d^2$ 时，称其为完全平方数。

数据规模

所有输入均为整数。

$2\leq N\leq 2×10^5$

$0\leq A_i\leq 2×10^5$

输入

输入来自标准输入，格式如下:

$N$

$A_1\ \ldots A_N$

输出

打印答案。

5
0 3 2 8 12

6

六对整数 $(i,j)=(1,2),(1,3),(1,4),(1,5),(2,5),(3,4)$ 满足条件。

例如，$A_2A_5=36$，并且 36 是平方数，因此对 $(i,j)=(2,5)$ 满足条件。

8
2 2 4 6 3 100 100 25

7