You are given n positive integers a_1, …, a_n, and an integer k ≥ 2. Count the number of pairs i, j such that 1 ≤ i < j ≤ n, and there exists an integer x such that a_i ⋅ a_j = x^k.

Input

The first line contains two integers n and k (2 ≤ n ≤ 10^5, 2 ≤ k ≤ 100).

The second line contains n integers a_1, …, a_n (1 ≤ a_i ≤ 10^5).

Output

Print a single integer — the number of suitable pairs.

Example

Input


6 3
1 3 9 8 24 1


Output


5

Note

In the sample case, the suitable pairs are:

  * a_1 ⋅ a_4 = 8 = 2^3;
  * a_1 ⋅ a_6 = 1 = 1^3;
  * a_2 ⋅ a_3 = 27 = 3^3;
  * a_3 ⋅ a_5 = 216 = 6^3;
  * a_4 ⋅ a_6 = 8 = 2^3.
from collections import Counter as C
NN = 100000
X = [-1] * (NN+1)
L = [[] for _ in range(NN+1)]
k = 2
while k <= NN:
    X[k] = 1
    L[k].append(k)
    for i in range(k*2, NN+1, k):
        X[i] = 0
        L[i].append(k)
    d = 2
    while k**d <= NN:
        for i in range(k**d, NN+1, k**d):
            L[i].append(k)
        d += 1
    while k <= NN and X[k] >= 0:
        k += 1
P = [i for i in range(NN+1) if X[i] == 1]

K = 4
def free(ct):
    a = 1
    for c in ct:
        a *= c ** (ct[c] % K)
    return a
def inv(ct):
    a = 1
    for c in ct:
        a *= c ** (-ct[c] % K)
    return a

N, K = map(int, input().split())
A = [int(a) for a in input().split()]
D = {}
ans = 0
for a in A:
    c = C(L[a])
    invc = inv(c)
    if invc in D:
        ans += D[invc]
    freec = free(c)
    if freec in D:
        D[freec] += 1
    else:
        D[freec] = 1

print(ans)

