M. Math
time limit per test
2 seconds
memory limit per test
512 mebibytes
input
standard input
output
standard output

You are given an array $$$a$$$ of $$$n$$$ distinct positive integers. Find the number of pairs $$$(i, j)$$$ with $$$1 \le i, j \le n$$$ for which the number $$$a_i^2 + a_j$$$ is a square of an integer.

Input

The first line of the input contains a single integer $$$n$$$ ($$$1 \le n \le 10^6$$$), the size of the array.

The second line of the input contains $$$n$$$ distinct positive integers $$$a_1, \ldots, a_n$$$ ($$$1 \le a_i \le 10^6$$$).

Output

Output a single integer: the answer to the problem.

Example
Input
5
1 2 3 4 5
Output
2
Note

In the example, there are two such pairs, corresponding to $$$1^2 + 3 = 4 = 2^2$$$ and $$$2^2 + 5 = 9 = 3^2$$$.