You 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$.


-----Input-----

The 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$).


-----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 \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$.

Difficulty: interview

Starter code:

Solutions:
def f(n):
    Ans = []
    d = 2
    while d * d <= n:
        if n % d == 0:
            Ans.append(d)
            n //= d
        else:
            d += 1
    if n > 1:
        Ans.append(n)
    return Ans


n, k = list(map(int, input().split()))
arr = list(map(int, input().split()))

m = {}
c = 0
for i in arr:
    r = {}
    d = 2
    while d * d <= i:
        if i % d == 0:
            r[d] = (r.get(d, 0) + 1) % k
            i //= d
        else:
            d += 1
    if i > 1:
        r[i] = (r.get(i, 0) + 1) % k
    r = tuple([x for x in list(r.items()) if x[1]])
    r2 = tuple([(x[0], k - x[1]) for x in r])
    c += m.get(r2, 0)
    m[r] = m.get(r, 0) + 1
print(c)


from collections import defaultdict
import math
n,k = list(map(int,input().split()))
a = list(map(int,input().split()))

ans = 0
hm = defaultdict(int)

for i in range(n):
    x = 2
    t = []
    t1 = []
    y = a[i]
    while x<=math.sqrt(a[i]):
        if a[i]%x==0:
            c = 0
            while y%x==0:
                y = y//x
                c += 1
            if c%k>0:
                t.append((x,c%k))
                t1.append((x,k-(c%k)))
        x += 1
    if y>1:
        t.append((y,1%k))
        t1.append((y,k-(1%k)))

    ans += hm[tuple(t1)]
    hm[tuple(t)] += 1

print(ans)
        


from collections import defaultdict

total = 0 
import math
dic = defaultdict(int)
n, k = list(map(int, input().split()))
z = list(map(int, input().split()))
for ii in z:

    i = ii
    x = []
    x2=[]
    a = 2
    while a<=math.sqrt(ii):
        co = 0
        while i % a == 0:
            i = i//a
            co += 1
        co=co%k
        if co:
            x.append((a, co))
            x2.append((a, k-co))
        a += 1
    if i>1:
        x.append((i,1))
        x2.append((i,k-1))
    # print(i)
    # print(x)
    # print(dic)
    dic[tuple(x)] += 1
    total += dic[tuple(x2)]
        # print(f"ans:{x} and {inver(x)}")
    if(x2 == x):
        total-=1



# print(x)
print(total)


n,k=list(map(int,input().split()))
arr=list(map(int,input().split()))
ans=0
d={}
for i in range(n):
	x=2
	a=[]
	b=[]
	y=arr[i]
	while x*x<=arr[i]:
		if arr[i]%x==0:
			c=0
			while y%x==0:
				y=y//x
				c+=1
			if c%k>0:
				a.append((x,c%k))
				b.append((x,k-(c%k)))
		x+=1
	if y>1:
		a.append((y,1%k))
		b.append((y,k-(1%k)))
	try:
		ans+=d[tuple(b)]
	except:
		pass
	try:
		d[tuple(a)]+=1
	except:
		d[tuple(a)]=1
print(ans)


n, k = map(int, input().split())
*a, = map(int, input().split())
d = {}
ans = 0
for i in a:
    x, j, tmp1, tmp2 = i, 2, [], []
    while j * j <= i:
        c = 0
        while x % j == 0:
            c += 1
            x //= j
        if c % k:
            tmp2.append((j, k - c % k))
            tmp1.append((j, c % k))
        j += 1
    if x > 1:
        tmp1.append((x, 1))
        tmp2.append((x, k - 1))
    tmp1, tmp2 = tuple(tmp1), tuple(tmp2)
    ans += d.get(tmp2, 0)
    d[tmp1] = d.get(tmp1, 0) + 1
print(ans)

import math
from collections import Counter
 
n, k = map(int, input().split())
a = list(map(int, input().split()))
 
ans = 0
prev = Counter()
for x in a:
	sig = []
	p = 2
	while p <= math.sqrt(x):
		cnt = 0
		while x % p == 0:
			cnt += 1
			x = x // p
 
		cnt = cnt % k
		if cnt > 0:
			sig.append((p, cnt))
 
		p += 1
 
	if x > 1:
		sig.append((x, 1))
 
	com_sig = []
	for p, val in sig:
		com_sig.append((p, (k - val) % k))
 
	ans += prev[tuple(sig)]
	prev[tuple(com_sig)] += 1
 
print(ans)

n, k = list(map(int, input().split()))

a = list(map(int, input().split()))
d = {}
ans = 0

for el in a:
    i = 2
    a = []
    b = []
    while i*i <= el:
        cnt = 0
        while not(el%i):
            el //= i
            cnt += 1
        if cnt%k:
            a.append((i, cnt%k))
            b.append((i, k-(cnt%k)))
        i += 1
    
    if el > 1:
        a.append((el, 1))
        b.append((el, k-1))

    a = tuple(a)
    b = tuple(b)

    ans += d.get(b, 0)
    d[a] = d.get(a, 0)+1
    
print(ans)


# -*- coding:utf-8 -*-

"""

created by shuangquan.huang at 2/11/20

"""

import collections
import time
import os
import sys
import bisect
import heapq
from typing import List
import math


def factors(val):
    wc = []
    for i in range(2, int(math.sqrt(val)) + 2):
        if i > val:
            break
        if val % i == 0:
            c = 0
            while val % i == 0:
                c += 1
                val //= i
            wc.append((i, c))
    if val > 1:
        wc.append((val, 1))
    return wc


def expand(fc, maxd, k):
    def dfs(index, mul):
        if index >= len(fc):
            return [mul]
        
        w, c = fc[index]
        d = k - (c % k) if c % k != 0 else 0
        x = []
        t = mul * (w ** d)
        while t <= maxd:
            x.extend(dfs(index + 1, t))
            d += k
            t *= w**k
        
        return x
        
    return dfs(0, 1)
    
def solve(N, K, A):
    wc = collections.defaultdict(int)
    ans = 0
    for v in A:
        fc = factors(v)
        fc = [(f, c % K) for f, c in fc if c % K != 0]
        key = '_'.join(['{}+{}'.format(f, c) for f, c in fc])
        cov = [(f, K-c) for f, c in fc]
        ckey = '_'.join(['{}+{}'.format(f, c) for f, c in cov])
        ans += wc[ckey]
        wc[key] += 1

    return ans
    
N, K = map(int, input().split())
A = [int(x) for x in input().split()]
print(solve(N, K, A))

from math import *

n, k = list(map(int, input().split()))
a = [int(i) for i in input().split()]
ma = max(a)

p = []
prime = [True] * (ma + 1)
prime[0] = False
prime[1] = False
for i in range(2, ma + 1):
    if prime[i]:
        p.append(i)
        if i**2 <= n:
            for j in range(i**2, ma + 1, i):
                prime[j] = False


def factor(x):
    res = {}
    sq = ceil(sqrt(x))
    for i in p:
        if i > sq or x <= 1:
            break
        if x % i == 0:
            res[i] = 0
            while x % i == 0:
                res[i] += 1
                x //= i
    if x > 1:
        res[x] = 1
    nres = []
    for j in res:
        if res[j] % k > 0:
            nres.append((j, res[j] % k))
    
    return tuple(nres)

d = {}
for i in range(n):
    f = factor(a[i])
    #print(f, a[i])
    if f not in d:
        d[f] = 1
    else:
        d[f] += 1
        
ans = 0
#print(d)
for x in d:
    y = []
    for i in x:
        y.append((i[0], k - i[1]))
    y = tuple(y)
    if y in d:
        if y != x:
            ans += d[x] * d[y]
        else:
            ans += d[x] * (d[y] - 1)
    #print(x, y, ans)

print(ans//2)


from collections import defaultdict

n, k = map(int, input().split())
a = list(map(int, input().split()))

n = int(max(a)**.5)
mark = [True]*(n+1)
primes = []
for i in range(2,n+1):
	if mark[i]:
		primes.append(i)
		for j in range(i, n+1, i): mark[j] = False
del mark
d = defaultdict(int)
ans = 0

for i in a:
	t, t1 = (), ()
	for j in primes:
		if i == 1:break
		elif i%j == 0:
			x = 0
			while i%j==0: 
				i//=j
				x += 1
			z = x%k
			if z:
				t += (j,z)
				t1 += (j,k-z)
	if i != 1:
		t += (i,1)
		t1 += (i,k-1)

	ans += d[t1]
	d[t] += 1
print(ans)

from collections import defaultdict

n, k = map(int, input().split())
a = list(map(int, input().split()))

n = int(max(a)**.5)
mark = [True]*(n+1)
primes = []
for i in range(2,n+1):
	if mark[i]:
		primes.append(i)
		for j in range(i, n+1, i): mark[j] = False
d = defaultdict(int)
ans = 0

for i in a:
	t, t1 = (), ()
	for j in primes:
		if i == 1:break
		elif i%j == 0:
			x = 0
			while i%j==0: 
				i//=j
				x += 1
			z = x%k
			if z:
				t += (j,z)
				t1 += (j,k-z)
	if i != 1:
		t += (i,1)
		t1 += (i,k-1)

	ans += d[t1]
	d[t] += 1
print(ans)

from collections import defaultdict
n, k = map(int, input().split())
a = list(map(int, input().split()))

n = int(max(a)**.5)
mark = [True]*(n+1)
primes = []
for i in range(2,n+1):
	if mark[i]:
		primes.append(i)
		for j in range(i, n+1, i): mark[j] = False

d = defaultdict(int)

ans = 0
for i in a:
	t, t1 = [], []
	for j in primes:
		if i%j == 0:
			x = 0
			while i%j==0: 
				i//=j
				x += 1
			z = x%k
			if z:
				t.append((j,z))
				t1.append((j,k-z))
		elif i == 1:break
	if i != 1:
		t.append((i,1))
		t1.append((i,k-1))

	t = tuple(t)
	t1 = tuple(t1)

	ans += d[t1]
	d[t] += 1
print(ans)

import math


def fac(a):
    ans = {}

    for i in range(2, int(math.sqrt(a)) + 1):
        if a % i == 0:
            ans[i] = 0
            while a % i == 0:
                a //= i
                ans[i] += 1

    ans[a] = 1

    return ans


def inverse(a, k):
    buf = {}

    for j in a.keys():
        buf[j] = (k - a[j] % k) % k

    return buf


def normal(a, k):
    buf = {}

    for j in a.keys():
        buf[j] = a[j] % k

    return buf


def getHash(d):
    ans = 1
    for i in d.keys():
        ans *= i ** d[i]
    return ans


n, k = map(int, input().split(' '))

a = [i for i in map(int, input().split(' '))]

b = [i for i in map(fac, a)]

factors = {}

for i in b:
    buf = getHash(inverse(i, k))
    if buf in factors.keys():
        factors[buf] += 1
    else:
        factors[buf] = 1

ans = 0

for i in range(len(b)):
    b[i] = normal(b[i], k)
    if getHash(b[i]) == getHash(inverse(b[i], k)):
        ans -= 1

for i in map(getHash, b):
    if i in factors.keys():
        ans += factors[i]

print(ans // 2)

import sys
input =  lambda: sys.stdin.readline().rstrip("\r\n")

n, k = map(int, input().split())
a = list(map(int, input().split()))


def factors(n, k):
    i = 2
    sq = int(n**0.5)+1
    di={}
    while n != 1:
        if n % i == 0:
            cur = 0
            while n % i == 0:
                n = n // i
                cur += 1
            if cur % k != 0:
                di[i] = cur % k
        i += 1
        if i > sq:break
    if n != 1:
        di[n] = 1
    return "|".join("%d:%d" % (i, di[i]) for i in di)

ft = {}
di = {}

for i in a:
    ft[i] = factors(i, k)
    di[ft[i]] = 1 if ft[i] not in di else di[ft[i]] + 1

ans = 0
for i in a:
    ftt = ft[i]
    if ftt == "":
        ans += di[ftt] - 1
    else:
        dx = {}
        for oo in ftt.split("|"):
            x, y = map(int, oo.split(":"))
            dx[x] = - y % k
        ftt2 = "|".join("%d:%d" % (i, dx[i]) for i in dx)
        if ftt == ftt2:
            ans += di[ftt2] - 1
        else:
            if ftt2 in di:
                ans += di[ftt2]

print(ans//2)

from collections import defaultdict as dc
dic=dc(lambda:0)
x,y=list(map(int,input().split()))
s=list(map(int,input().split()))
siv=[0]*(max(s)+1)
ln=len(siv)
siv[1]=1;

for n in range(2,ln):
    if siv[n]==0:
        siv[n]=n
        for k in range(2*n,ln,n):
            if siv[k]==0:
                siv[k]=n

def prf(x):
    dic=dc(lambda:0)
    while x>1:
        d=siv[x]
        dic[siv[x]]+=1
        x//=siv[x]
    
    return dic

def req(dic,k):
    cur=dic
    for n in cur:
        cur[n]%=k
    for n in cur:
        cur[n]=(k-cur[n])%k
    tot=1
    for n in cur:
        tot*=(n**cur[n])
    return tot

def conv(x,k):
    dicc=prf(x)
    for n in dicc:
        dicc[n]%=k
    tot=1
    for n in dicc:
        tot*=(n**dicc[n])

    return tot

res=0
for n in s:
    re=req(prf(n),y)
    res+=dic[re]
    dic[conv(n,y)]+=1

print(res)


from math import sqrt
def gd(n, k):
    ans = 1
    obrans = 1
    for i in range(2, int(sqrt(n) + 1)):
        j = 0
        while n % i == 0:
            j += 1
            n //= i
        ans *= pow(i, j%k)
        obrans *= pow(i, (-j)%k)
    ans *= n
    obrans *= pow(n, (k-1))
    return ans, obrans
n, k = map(int,input().split())
oba = set()
dct = {}
for i in list(map(int,input().split())):
    a,b = gd(i, k)
    dct[a] = dct.get(a, 0) + 1
    a,b = min(a,b), max(a,b)
    oba.add((a,b))
ans = 0
for i, j in oba:
    if i == j:
        ans += (dct.get(i, 0)  * dct.get(j, 0) - dct.get(i, 0)) // 2
    else:
        ans += dct.get(i, 0) * dct.get(j, 0)
print(ans)

import itertools as it
from collections import defaultdict
import os
import sys


def sieve(n):
    is_prime = [True] * n

    for candidate in it.chain([2], list(range(3, int(n ** 0.5) + 1, 2))):
        if is_prime[candidate]:
            for k in range(2 * candidate, n, candidate):
                is_prime[k] = False

    primes = [idx for idx, k in enumerate(is_prime) if idx >= 2 and k]
    return primes


def factorize(n, primes, k):
    factors = []
    number = n
    for f in primes:
        count = 0
        while number % f == 0:
            count += 1
            number //= f

        if count % k:
            factors.append((f, count % k))

        if f > number:
            break

    if number > 1:
        factors.append((number, 1))

    return tuple(factors)


def solve(arr, k):
    total = 0
    d = defaultdict(int, {})
    primes = sieve(int(1e5 ** 0.5) + 10)
    for a in arr:
        fac = factorize(a, primes, k)
        fac_complement = tuple((f, k - count) for f, count in fac)
        total += d[fac_complement]
        d[fac] += 1

    return total


def pp(input):
    # T = int(input())
    # for t in range(T):
    n, k = list(map(int, input().strip().split()))
    arr = list(map(int, input().strip().split()))
    print(solve(arr, k))


if "paalto" in os.getcwd():
    from string_source import string_source, codeforces_parse

    pp(
        string_source(
            """6 3
1 3 9 8 24 1"""
        )
    )
else:
    pp(sys.stdin.readline)


from collections import defaultdict
import sys as _sys


def main():
    n, k = _read_ints()
    a = tuple(_read_ints())
    result = find_good_pairs_n(a, k)
    print(result)


def _read_line():
    result = _sys.stdin.readline()
    assert result[-1] == "\n"
    return result[:-1]


def _read_ints():
    return list(map(int, _read_line().split()))


def find_good_pairs_n(sequence, k):
    sequence = tuple(sequence)
    factors_seq = tuple(map(_find_prime_factors, sequence))
    
    factors_seq = [[(kv[0], kv[1] % k) for kv in list(factors.items())] for factors in factors_seq]
    factors_seq = [[kv for kv in factors if kv[1] > 0] for factors in factors_seq]
    factors_seq = list(map(sorted, factors_seq))
    factors_seq = tuple(map(tuple, factors_seq))
    
    counter = defaultdict(int)
    for factors in factors_seq:
        counter[factors] += 1
    
    result = 0
    for factors in factors_seq:
        necessary_factors = tuple((factor, k - amount) for factor, amount in factors)
        result += counter[necessary_factors]
        if factors == necessary_factors:
            result -= 1
    
    assert result % 2 == 0
    result //= 2
    return result


def _find_prime_factors(x):
    result = dict()
    
    if x % 2 == 0:
        factor_2_n = 0
        while x & 1 == 0:
            x >>= 1
            factor_2_n += 1
        result[2] = factor_2_n
    
    factor = 3
    while x != 1 and factor * factor <= x:
        if x % factor == 0:
            factor_n = 0
            while x % factor == 0:
                x //= factor
                factor_n += 1
            result[factor] = factor_n
        factor += 2

    if x != 1:
        result[x] = 1

    return result


def __starting_point():
    main()

__starting_point()

from collections import defaultdict

class Primes():
    def __init__(self, N):
        self.N = N
        self.prime = {i for i in range(2, self.N+1)}
        self.spf = [-1]*(N + 1)
        for i in range(2, self.N+1):
            if i in self.prime:
                self.spf[i] = i
                for j in range(i*2, self.N+1, i):
                    if j in self.prime:
                        self.spf[j] = i
                        self.prime.remove(j)

    def fact(self,Number):
        v = Number
        d = defaultdict(int)
        while v > 1:
            x = self.spf[v]
            d[x] += 1
            v//=x
        return d


P = Primes(10**5)

n,k = list(map(int,input().split()))
a = list(map(int,input().split()))
cnt = [0]*(10**5 + 1)
for v in a:
    cnt[v] += 1

ans = 0
for v in a:
    cnt[v] -= 1
    d = P.fact(v)
    res = 1
    for num,order in list(d.items()):
        res *= pow(num,(k-order%k)%k)
    if res <= 10**5:
        for i in range(1,1000):
            if pow(i,k)*res > 10**5:
                break
            ans += cnt[pow(i,k)*res]
print(ans)