CF1225D Power Products

给定 $n$ 个正整数 $a_1,a_2,\dots,a_n$ 和一个的正整数 $k$（$k\geq2$）。现在请你求出有多少组 $(i,j)$（$1 \le i < j \le n$），满足存在一个整数 $x$ 满足 $a_i \times a_j = x^k $。

输入第一行是两个正整数 $n$ 和 $k$（保证 $2 \le n \le 10^5 , 2 \le k \le 100$）； 第二行为 $n$ 个正整数 $a_1,a_2,\dots,a_n$（保证 $1 \le a_i \le 10^5$）。

输出一个整数，表示有多少满足条件的组合。

样例中有以下几组满足条件的组合： 1. $a_1 \times a_4 = 8 = 2^3$ 2. $a_1 \times a_6 =1 = 1^3$ 3. $a_2 \times a_3 = 27 = 3^3$ 4. $a_3 \times a_5 = 216 = 6^3$ 5. $a_4 \times a_6 = 8 = 2^3$ 一共五组，所以输出为 $5$。