题目描述

33DAI 有 $n$ 个正整数 $a_1, a_2, \dots, a_n$。

他想知道：有多少对 $(i, j)$ 满足 $1 \le i < j \le n$，且 $a_i \times a_j$ 是完全平方数？

输入格式

第一行一个整数 $n$。

第二行 $n$ 个整数 $a_1, a_2, \dots, a_n$，相邻两个整数之间用一个空格隔开。

输出格式

输出一行一个整数，表示满足条件的数对个数。

4
1 2 8 18

3

样例 1 解释

满足条件的数对有：

• $2 \times 8 = 16 = 4^2$；
• $2 \times 18 = 36 = 6^2$；
• $8 \times 18 = 144 = 12^2$。

$1$ 与其它数的乘积都不是完全平方数，所以答案是 $3$。

6
12 3 27 4 9 2

4

样例 2 解释

满足条件的数对有：

• $12 \times 3 = 36 = 6^2$；
• $12 \times 27 = 324 = 18^2$；
• $3 \times 27 = 81 = 9^2$；
• $4 \times 9 = 36 = 6^2$。

其余数对的乘积都不是完全平方数，所以答案是 $4$。

样例 3

见 pairsq3.in 与 pairsq3.ans。

样例 4

见 pairsq4.in 与 pairsq4.ans。

数据范围

对于全部测试数据，保证：

• $1 \le n \le 2 \times 10^5$；
• $1 \le a_i \le 10^7$。

子任务

本题共 20 个测试点，按测试点计分：

每个测试点单独评分，全部测试点的得分之和即为本题得分。