【文件读写】本题使用文件读写：输入文件 reson.in，输出文件 reson.out。

时间限制：1000ms　内存限制：512MB

题目描述

程老师最近迷上了零件组装。他手上有 $n$ 个零件，每个零件上都标有一个正整数参数，第 $i$ 个零件的参数为 $a_i$。

程老师发现，有些零件之间存在一种奇妙的"共鸣"现象。他给出了如下定义：两个零件能够产生共鸣，当且仅当它们的参数乘起来恰好是一个完全平方数。也就是说，把两个零件的参数相乘，得到的结果能够表示成某个正整数的平方。

程老师想知道，在他手上的这 $n$ 个零件中，一共能找出多少对共鸣的零件。这里"一对"指的是两个不同的零件，且 $(i, j)$ 和 $(j, i)$ 算作同一对，即只统计满足 $i < j$ 的配对。

由于零件数量可能很多，程老师希望你能高效地帮他算出结果。

输入格式

从文件 reson.in 中读入数据。

第一行一个正整数 $n$，表示零件的个数。

第二行 $n$ 个正整数 $a_1, a_2, \ldots, a_n$，表示每个零件的参数。

输出格式

输出到文件 reson.out 中。

一行一个整数，表示共鸣的零件对数。

数据范围

对于所有测试点，保证：

• $1 \le n \le 10^5$。
• $1 \le a_i \le 10^6$。

各测试点的详细限制如下：

特殊性质 A：$a_i$ 只有两种取值。

特殊性质 B：$a_i \le 100$。

样例

样例 1 输入

4
1 2 8 3

样例 1 输出

1

样例 2 输入

3
4 9 2

样例 2 输出

1

样例 3 输入

4
2 8 18 32

样例 3 输出

6

样例解释

对于样例 1，所有可能的配对及其乘积为：$(1,2)$ 得 $2$，$(1,8)$ 得 $8$，$(1,3)$ 得 $3$，$(2,8)$ 得 $16$，$(2,3)$ 得 $6$，$(8,3)$ 得 $24$。其中只有 $16 = 4^2$ 是完全平方数，因此只有一对共鸣。