给你 $$$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$$$。
输入
第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$2 \leq n \leq 10^5$$$, $$$2 \leq k \leq 100$$$)。
第二行包含 $$$n$$$ 整数 $$$a_1, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^5$$$)。
输出
打印一个整数——合适的对的数量。
示例
输入 #1
6 3 1 3 9 8 24 1
输出 #1
5
注意
在示例案例中,合适的对是:
- $$$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$$$。