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.
#include <bits/stdc++.h>
using namespace std;
const long long maxn = 102000;
long long n, k, a[maxn], pri[maxn], vis[maxn], pcnt, cnt[maxn], nd[maxn];
long long pkt[maxn][102];
long long bu(long long x, bool chk = false) {
  long long ret = 1;
  auto deal = [&](long long fac, long long deg) {
    deg %= k;
    if (deg == 0)
      return 1ll;
    else
      return pkt[fac][k - deg];
  };
  while (x != 1) {
    long long d = vis[x], deg = 0, so;
    while (x % d == 0) x /= d, deg++;
    if (chk) {
      if (deg % k != 0) return -1;
    } else {
      so = deal(d, deg);
      if (so == -1)
        return -1;
      else {
        ret *= so;
        if (ret >= maxn) return -1;
      }
    }
  }
  return ret;
}
long long yu(long long x) {
  long long ret = 1;
  auto deal = [&](long long fac, long long deg) {
    deg %= k;
    return pkt[fac][deg];
  };
  while (x != 1) {
    long long d = vis[x], deg = 0, so;
    while (x % d == 0) x /= d, deg++;
    so = deal(d, deg);
    if (so == -1)
      return -1;
    else {
      ret *= so;
      if (ret >= maxn) return -1;
    }
  }
  return ret;
}
signed main() {
  memset(pkt, -1, sizeof pkt);
  for (long long i = 2; i < maxn; ++i) {
    pkt[i][0] = 1;
    for (long long j = 1; 1LL * pkt[i][j - 1] * i < maxn; ++j)
      pkt[i][j] = pkt[i][j - 1] * i;
    if (!vis[i]) pri[++pcnt] = i, vis[i] = i;
    for (long long j = 1; j <= pcnt && i * pri[j] < maxn; ++j) {
      vis[i * pri[j]] = pri[j];
      if (i % pri[j] == 0) break;
    }
  }
  scanf("%lld%lld", &n, &k);
  for (long long i = 1; i <= n; ++i) {
    scanf("%lld", &a[i]);
    cnt[yu(a[i])]++;
    long long b = bu(a[i]);
    if (b != -1) nd[b]++;
  }
  long long ans = 0;
  for (long long i = 1; i <= 100000; ++i)
    if (nd[i]) {
      ans += 1LL * nd[i] * cnt[i];
    }
  for (long long i = 1; i <= 100000; ++i)
    if (yu(i) == bu(i)) {
      ans -= cnt[i];
    }
  ans /= 2;
  printf("%lld\n", ans);
  return 0;
}
