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 double eps = 1e-10;
const double Dlt = 0.97;
const int inf = 0x3f3f3f3f;
const long long INF = 1e18;
const int maxn = 100000 + 10;
const int maxm = 1000000 + 10;
const int mod = 1000000000 + 7;
int gcd(long long a, long long b) { return b ? gcd(b, a % b) : a; }
inline long long read() {
  char ch = getchar();
  long long x = 0, f = 1;
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while ('0' <= ch && ch <= '9') {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  return x * f;
}
int n, k;
map<vector<pair<int, int>>, int> cnt;
vector<pair<int, int>> p1, p2;
int a[maxn];
int vis[maxn + 5];
int minprime[maxn];
int prime[maxn];
void sieve(int n) {
  vis[1] = 1;
  for (int i = 2; i <= n; ++i) {
    if (!vis[i]) {
      minprime[i] = i;
      prime[++k] = i;
    }
    for (long long j = 1; j <= k && (long long)i * prime[j] <= n; j++) {
      minprime[(long long)i * prime[j]] = prime[j];
      vis[(long long)i * prime[j]] = 1;
      if (!(i % prime[j])) break;
    }
  }
}
void divide(int x) {
  if (!vis[x]) {
    p1.push_back(make_pair(x, 1));
    p2.push_back(make_pair(x, k - 1));
    return;
  }
  while (x > 1) {
    int t = minprime[x], u = 0;
    while (x % t == 0 && x != 1) {
      x /= t;
      u = (u + 1) % k;
    }
    if (u != 0) {
      p1.push_back(make_pair(t, u));
      p2.push_back(make_pair(t, k - u));
    }
  }
}
int main() {
  sieve(100000);
  scanf("%d %d", &n, &k);
  for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
  long long ans = 0;
  long long res1 = 0;
  for (int i = 1; i <= n; ++i) {
    p1.clear();
    p2.clear();
    divide(a[i]);
    ans += cnt[p2];
    cnt[p1]++;
  }
  printf("%lld\n", ans);
}
