Cho dãy gồm ~n~ số nguyên dương ~a_1, a_2, \dots, a_n~ và một số nguyên ~k~. Hãy đếm số cặp chỉ số ~(i, j)~ (với ~i < j~) sao cho tồn tại số nguyên dương ~x~ thỏa mãn ~a_i \times a_j = x^k~, tức tích hai phần tử là lũy thừa bậc ~k~ của một số nguyên dương.

Dữ liệu

• Dòng đầu tiên chứa hai số nguyên dương ~n~ và ~k~ (~1 \le n \le 10^5~, ~2 \le k \le 100~): số phần tử của dãy và số mũ.
• Dòng thứ hai chứa ~n~ số nguyên dương ~a_1, a_2, \dots, a_n~ (~1 \le a_i \le 10^5~).

Kết quả

• In ra một số nguyên duy nhất là số cặp thỏa mãn yêu cầu.

Ví dụ

POWER.INP

6 3
1 3 9 8 24 1

POWER.OUT

5

Giải thích: Có 5 cặp thỏa mãn:

• ~a_1 \times a_4 = 8 = 2^3~
• ~a_1 \times a_6 = 1 = 1^3~
• ~a_2 \times a_3 = 27 = 3^3~
• ~a_3 \times a_5 = 216 = 6^3~
• ~a_4 \times a_6 = 8 = 2^3~

Giới hạn

• Subtask 1 (50% số điểm): ~n \le 1000~.
• Subtask 2 (50% số điểm): không có ràng buộc gì thêm.