Cho dãy số nguyên dương ~a = a_1, a_2, \ldots, a_n~. Hãy đếm số cặp chỉ số ~(i, j)~ thỏa mãn:

• ~1 \le i < j \le n~
• ~\dfrac{\mathrm{LCM}(a_i, a_j)}{\mathrm{GCD}(a_i, a_j)}~ là số chính phương

Trong đó:

• ~\mathrm{LCM}~: là ký hiệu bội số chung nhỏ nhất. ~\mathrm{LCM}(a_i, a_j)~ là số nguyên dương nhỏ nhất chia hết cho cả ~a_i~ và ~a_j~.
• ~\mathrm{GCD}~: là ký hiệu ước số chung lớn nhất. ~\mathrm{GCD}(a_i, a_j)~ là số nguyên dương lớn nhất mà là ước của cả ~a_i~ và ~a_j~.
• Số chính phương: là giá trị bình phương của một số tự nhiên (Ví dụ: ~1, 4, 9, 16, \ldots~).

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên dương ~n~ (~1 \le n \le 10^6~).
• Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, \ldots, a_n~ (~1 \le a_i \le 10^6~, ~1 \le i \le n~).

Kết quả

• Một số nguyên duy nhất là số cặp chỉ số ~(i, j)~ thỏa mãn điều kiện đặt ra.

Ví dụ

Đầu vào:

5
2 8 3 12 50

Đầu ra:

4

Giải thích: Các cặp thỏa mãn là:

1. ~(2, 8)~: ~8/2 = 4~ (~2^2~)
2. ~(2, 50)~: ~50/2 = 25~ (~5^2~)
3. ~(8, 50)~: ~200/2 = 100~ (~10^2~)
4. ~(3, 12)~: ~12/3 = 4~ (~2^2~)

Giới hạn

• ~1 \le n \le 10^6~
• ~1 \le a_i \le 10^6~

Điểm của một subtask chỉ được tính khi tất cả các test thuộc subtask đó đều đúng. Lưu ý rằng kết quả có thể vượt quá phạm vi kiểu số nguyên 32 bit.