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;
template <typename T>
int sign(T a) {
  if (a == 0) return 0;
  return (a > 0 ? 1 : -1);
}
template <typename T1, typename T2>
T2 mod(T1 x, T2 MOD) {
  if (x < 0) x += MOD;
  if (x >= MOD) x -= MOD;
  return x;
}
template <typename T>
T sqr(T a) {
  return a * a;
}
template <typename T>
bool uax(T& a, const T b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}
template <typename T>
bool uin(T& a, const T b) {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
}
template <typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& p) {
  in >> p.first >> p.second;
  return in;
}
template <typename T1, typename T2>
ostream& operator<<(ostream& out, pair<T1, T2>& p) {
  out << '(' << p.first << ' ' << p.second << ')';
  return out;
}
mt19937_64 gen_rand;
const int N = (int)3e5 + 7;
const int LOG = 31;
const int N_ = (int)507;
const int MAXN = (int)8e5 + 7;
const int MOD = (int)1e9 + 7;
const int INF = (int)2e9 + 7;
const int CONST = 5000;
const long long LINF = (int64_t)1e10;
const long double PI = 3.1415926535897932384626433832795;
const long double EPS = 5e-1;
int n, k, a[N], cnt[N];
int main() {
  cout << fixed << setprecision(20);
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  gen_rand.seed(time(0));
  cin >> n >> k;
  for (int i = 0; i < n; i++) cin >> a[i];
  if (k == 2) {
    map<int, int> cnt;
    for (int i = 0; i < n; i++) {
      int val = 1;
      for (int j = 2; j * j <= a[i]; j++) {
        int x = 0;
        while (a[i] % j == 0) x++, a[i] /= j;
        if (x & 1) val *= j;
      }
      if (a[i] != 1) val *= a[i];
      cnt[val]++;
    }
    long long ans = 0;
    for (auto it : cnt) {
      if (it.second == 1) continue;
      ans += 1LL * it.second * (it.second - 1) / 2;
    }
    cout << ans;
  } else {
    vector<long long> pw;
    bool fl = true;
    for (int i = 1;; i++) {
      long long x = 1;
      for (int j = 0; j < k; j++) {
        if (x * i > LINF) {
          fl = false;
          break;
        }
        x *= i;
      }
      if (!fl) break;
      pw.push_back(x);
    }
    long long ans = 0;
    for (int i = n - 1; i >= 0; i--) {
      for (long long x : pw) {
        if (x / a[i] > (int)1e5) break;
        if (x % a[i] == 0) ans += cnt[x / a[i]];
      }
      cnt[a[i]]++;
    }
    cout << ans;
  }
}
