Perfect Squares

Problem Description

Xiaoyang has a sequence $A$ of $n$ non-negative integers. He wants to know how many index pairs $\langle i,j \rangle$ with $1 \le i < j \le n$ satisfy that $A_i + A_j$ is a perfect square.

($x$ is a perfect square if there exists a non-negative integer $y$ such that $y \times y = x$.)

This problem has a corresponding multiple-choice / true-or-false question; see https://ti.luogu.com.cn/problemset/1143.

Input Format

The first line is a non-negative integer $n$, the number of non-negative integers.

The second line contains $n$ non-negative integers $A_1, A_2, \dots, A_n$, the elements of sequence $A$.

Output Format

Output one line containing one integer: the answer.

Sample Input

5
1 4 3 3 5

Sample Output

3

Sample Explanation

For the sample, the sequence is $[1, 4, 3, 3, 5]$, with $5$ numbers in total. The index pairs for which $A_i + A_j$ is a perfect square are:

• $\langle 1, 3 \rangle$: $1 + 3 = 4 = 2 \times 2$, a perfect square.
• $\langle 1, 4 \rangle$: $1 + 3 = 4$, also a perfect square (note that the sequence contains two $3$'s at different positions).
• $\langle 2, 5 \rangle$: $4 + 5 = 9 = 3 \times 3$, a perfect square.

None of the other pairs sum to a perfect square, so the answer is $3$.

Constraints

For all test data, $1 \le n \le 1000$ and $0 \le A_i \le 10^5$.