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;
using ll = long long;
using pii = pair<int, int>;
long long pk[100005];
int A[100005], C[100005], vis[100005];
vector<int> vec[100005];
int main() {
  ios_base::sync_with_stdio(0), cin.tie(0);
  int N, K;
  cin >> N >> K;
  for (int i = 1; i <= N; ++i) cin >> A[i], C[A[i]]++;
  for (int i = 1; i <= 100000; ++i) {
    for (int j = 1; j * j <= i; ++j) {
      if (i % j == 0) vec[i].push_back(j);
    }
    int t = 0;
    if (vec[i].back() * vec[i].back() == i) {
      t = vec[i].back();
      vec[i].pop_back();
    }
    for (int j = (int)vec[i].size() - 1; j >= 0; --j)
      vec[i].push_back(i / vec[i][j]);
    if (t) vec[i].push_back(t);
  }
  int bar = 100001;
  for (int i = 1; i <= 100000; ++i) {
    long long a = 1;
    int flag = 0;
    for (int j = 1; j <= K; ++j) {
      a *= i;
      if (a > 1e10) {
        flag = 1;
        break;
      }
    }
    if (flag) {
      bar = i;
      break;
    }
    pk[i] = a;
  }
  long long ans = 0;
  sort(A + 1, A + N + 1);
  if (K == 2) {
    for (int i = 1; i < bar; ++i) {
      for (auto j : vec[i]) {
        for (auto k : vec[i]) {
          if (j >= k) continue;
          if (1ll * i * k / j > 100000 || vis[i / k * j] == i) continue;
          vis[i / j * k] = i;
          vis[i / k * j] = i;
          ans += 1ll * C[i / j * k] * C[i / k * j];
        }
      }
      ans += 1ll * C[i] * (C[i] - 1) / 2;
    }
    cout << ans;
    return 0;
  }
  for (int i = 1; i <= N; ++i) {
    for (int j = 1; j < bar; ++j) {
      if (pk[j] % A[i]) continue;
      if (pk[j] == 1ll * A[i] * A[i])
        ans += C[A[i]] - 1;
      else if (pk[j] / A[i] <= 100000)
        ans += C[pk[j] / A[i]];
    }
  }
  cout << ans / 2;
  return 0;
}
