Making a Square

Interview

Time limit2sMemory limit512 MB

Summary

Given n distinct positive integers, count ordered pairs (i, j) such that a_i^2 + a_j is a perfect square.

Level: Medium6 of 10
Topics: Math, Number theory, Hash map, Brute force
Solved: No attempts yet

Problem

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 $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.

Hint

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

Examples1

Example 1
Input
```
5
1 2 3 4 5
```
Expected output
```
2
```