D. Power Productstime limit per test2 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard outputYou are given n positive integers a_1, \ldots, a_n, and an integer k \geq 2. Count the number of pairs i, j such that 1 \leq i < j \leq n, and there exists an integer x such that a_i \cdot a_j = x^k.InputThe first line contains two integers n and k (2 \leq n \leq 10^5, 2 \leq k \leq 100).The second line contains n integers a_1, \ldots, a_n (1 \leq a_i \leq 10^5).OutputPrint a single integer — the number of suitable pairs.ExampleInput
6 3
1 3 9 8 24 1
Output
5
NoteIn the sample case, the suitable pairs are: 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.
6 3
1 3 9 8 24 1

5 
['hashing', 'math', 'number theory', '*1800']