Вам дано \(n\) целых положительных чисел \(a_1, \ldots, a_n\) и целое \(k \geq 2\). Посчитайте количество пар \(i, j\), таких что \(1 \leq i < j \leq n\), а также существует целое \(x\), такое что \(a_i \cdot a_j = x^k\).
Выходные данные
Выведите одно число — количество подходящих пар.
Примечание
В примере подходят следующие пары:
- \(a_1 \cdot a_4 = 8 = 2^3\);
- \(a_1 \cdot a_6 = 1 = 1^3\);
- \(a_2 \cdot a_3 = 27 = 3^3\);
- \(a_3 \cdot a_5 = 216 = 6^3\);
- \(a_4 \cdot a_6 = 8 = 2^3\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6 3
1 3 9 8 24 1
|
5
|