Cho dãy số nguyên dương ~a_1, a_2, \ldots, a_n~. Hãy đếm số cặp chỉ số ~(i, j)~ sao cho ~1 \le i < j \le n~ và

~\dfrac{\operatorname{LCM}(a_i, a_j)}{\operatorname{GCD}(a_i, a_j)}~

là một số chính phương.

Trong đó:

• ~\operatorname{LCM}(a_i, a_j)~ là bội số chung nhỏ nhất của ~a_i~ và ~a_j~.
• ~\operatorname{GCD}(a_i, a_j)~ là ước số chung lớn nhất của ~a_i~ và ~a_j~.
• Số chính phương là bình phương của một số tự nhiên, ví dụ ~1, 4, 9, 16~.

Yêu cầu

Đếm số cặp chỉ số ~(i, j)~ thỏa mãn điều kiện trên.

Dữ liệu

• Dòng đầu chứa số nguyên dương ~n~.
• Dòng thứ hai chứa ~n~ số nguyên dương ~a_1, a_2, \ldots, a_n~.

Kết quả

In ra một số nguyên duy nhất là số cặp chỉ số thỏa mãn.

Ví dụ

Ví dụ 1

Input

5
2 8 3 12 50

Output

4

Giải thích

Ví dụ 1

Các cặp thỏa mãn là:

• ~(,2, 8,)~ vì ~8 / 2 = 4 = 2^2~.
• ~(,2, 50,)~ vì ~50 / 2 = 25 = 5^2~.
• ~(,8, 50,)~ vì ~200 / 2 = 100 = 10^2~.
• ~(,3, 12,)~ vì ~12 / 3 = 4 = 2^2~.

Ràng buộc và chấm điểm

Ràng buộc

• ~1 \le n \le 10^6~.
• ~1 \le a_i \le 10^6~ với mọi ~i~.

Chấm điểm

• ~20%~ số điểm ứng với các test có ~n \le 1000~.
• ~20%~ số điểm ứng với các test có mọi ~a_i~ là số chính phương.
• ~30%~ số điểm ứng với các test có ~a_i \le 1000~ với mọi ~i~.
• ~30%~ số điểm còn lại không có ràng buộc bổ sung.