Một số nguyên không âm ~a~ được gọi là số chính phương nếu tồn tại số nguyên không âm ~d~ sao cho ~a = d^2~. Chẳng hạn ~0, 1, 4, 36~ đều là số chính phương.

Cho dãy gồm ~n~ số nguyên không âm ~A_1, A_2, \ldots, A_n~. Hãy đếm số cặp chỉ số ~(i, j)~ thỏa mãn đồng thời hai điều kiện:

• ~1 \le i < j \le n~
• ~A_i \cdot A_j~ là một số chính phương.

Dữ liệu vào

• Dòng đầu tiên chứa một số nguyên ~n~ — độ dài của dãy.
• Dòng thứ hai chứa ~n~ số nguyên ~A_1, A_2, \ldots, A_n~.

Kết quả

In ra một số nguyên duy nhất là số cặp tìm được.

Ví dụ

Đầu vào:

5
0 3 2 8 12

Đầu ra:

6

Giải thích: Sáu cặp thỏa mãn là ~(1, 2), (1, 3), (1, 4), (1, 5), (2, 5), (3, 4)~. Ví dụ với cặp ~(2, 5)~ ta có ~A_2 \cdot A_5 = 3 \cdot 12 = 36 = 6^2~. Mọi cặp chứa ~A_1 = 0~ đều thỏa mãn vì tích bằng ~0 = 0^2~.

Đầu vào:

8
2 2 4 6 3 100 100 25

Đầu ra:

7

Giới hạn

• ~2 \le n \le 2 \cdot 10^5~
• ~0 \le A_i \le 2 \cdot 10^5~