T4 寻找完全平方数对

时间：1s

空间：256M

题目描述

小 S 最近正在学习完全平方数。这天，老师给了他一串数字，需要他在这些数中去找任意两个数，这两个数的乘积正好是完全平方数，小 S 做题后发现，这串数中满足条件的数对还挺多，接下去他想让你帮他找出这些数中一共有多少对数字可以组成完全平方数。

这是由 $n$ 个非负整数组成的数列 $a_1,a_2,......,a_{n-1},a_n$，你可以任意选择一对数字 $a_i$ 和 $a_j$ ，如果 $a_i \times a_j$ 的结果是一个完全平方数，那么这时的 $<a_i,a_j>$ 就是满足要求的一对。现在你需要去找出数列中一共有多少对数字能够组成完全平方数。

说明：完全平方是指用一个整数乘以自己，例如 $1 \times 1$ ，$2 \times 2$ ，$3 \times 3$ 等，依次类推。若一个数能表示成某个整数的平方形式，则称这个数为完全平方数。

假设非负整数 $x$ 可以用另外一个非负整数 $y$ 表示成 $x=y^2$ ，那么 $x$ 就是一个完全平方数。

输入格式

输入第 $1$ 行，一个正整数 $n$ ，表示接下去的数列中一共有多少个数字。

输入第 $2$ 行，$n$ 个非负整数，每个数字之间用一个空格间隔。

输出格式

输出 $1$ 行，一个整数，表示有多少对满足要求的数量。

样例

5
0 3 2 8 12

6

8
2 2 4 6 3 100 100 25

7

说明/提示

样例 1说明

满足条件的数对分别为$(0,3),(0,2),(0,8),(0,12),(3,12)$ 和 $(2,8)$

数据范围

$2 \le n \le 2 \times 10^5$ ，$0 \le a_i \le 2 \times 10^5$ 。