Counting Perfect Square Sum Pairs

Alice has a sequence A consisting of n non-negative integers. She needs to count the number of pairs \(\langle i, j \rangle\) (where \(1 \leq i < j \leq n\)) such that the sum \(A_i + A_j\) is a perfect square.

A number \(x\) is a perfect square if there exists a non-negative integer \(y\) such that \(y \times y = x\) (i.e., \(x = y^2\)).

Your task is to compute the total number of such valid pairs.

inputFormat

The first line contains an integer \(n\) indicating the number of elements in the sequence.

The second line contains \(n\) non-negative integers separated by spaces representing the sequence \(A\).

outputFormat

Output a single integer representing the number of pairs \(\langle i, j \rangle\) such that \(A_i + A_j\) is a perfect square.

sample

3
1 3 6

2