Reference: AtCoder ABC342 D — Square Pair

You are given a sequence of ~N~ non-negative integers:

~A_1, A_2, \ldots, A_N~

Find the number of pairs of indices ~(i, j)~ satisfying:

~1 \le i < j \le N~

such that ~A_i \times A_j~ is a perfect square.

A non-negative integer is called a perfect square if it can be written as ~d^2~ for some non-negative integer ~d~.

Input

• The first line contains one integer ~N~.
• The second line contains ~N~ integers: ~A_1, A_2, \ldots, A_N~.

Output

• Print the number of pairs satisfying the condition.

Constraints

• ~2 \le N \le 2 \times 10^5~
• ~0 \le A_i \le 2 \times 10^5~
• All input values are integers.

Example 1

Input:

5
0 3 2 8 12

Output:

6