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 int INF = 1000000001;
const long long int INFLL = 10000000001;
const long double EPS = 1e-6;
const int MAXN = 100005;
const int FACTORS_THRESHOLD = 100005;
int A[MAXN];
int T[MAXN];
long long int Power(int x, int y) {
  long long int r = 1;
  for (int i = 0; i < y; i++) {
    r = min(INFLL, r * x);
    if (r >= INFLL) break;
  }
  return r;
}
void Sieve(int n, vector<int>* primes, vector<int>* factors) {
  factors->resize(n + 1);
  for (int i = 2; i * i <= n; i++) {
    if ((*factors)[i] != 0) continue;
    for (int j = 2 * i; j <= n; j += i)
      if ((*factors)[j] == 0) (*factors)[j] = i;
  }
  (*factors)[1] = 1;
  for (int i = 2; i <= n; i++)
    if ((*factors)[i] == 0) {
      (*factors)[i] = i;
      primes->push_back(i);
    }
}
int SmallestFactor(long long int n, const vector<int>& primes,
                   const vector<int>& factors) {
  if (n <= FACTORS_THRESHOLD) {
    if (factors[n] == n) return 1;
    return factors[n];
  } else {
    for (int i = 0; i < primes.size(); i++)
      if (n % primes[i] == 0) return primes[i];
    return 1;
  }
}
void Factorize(long long int n, const vector<int>& primes,
               const vector<int>& factors,
               unordered_map<long long int, int>* factorization) {
  if (n == 1) return;
  long long int d = SmallestFactor(n, primes, factors);
  if (d == 1) {
    (*factorization)[n]++;
    return;
  }
  Factorize(d, primes, factors, factorization);
  Factorize(n / d, primes, factors, factorization);
}
unordered_map<long long int, int> Factorize(long long int n,
                                            const vector<int>& primes,
                                            const vector<int>& factors) {
  unordered_map<long long int, int> factorization;
  Factorize(n, primes, factors, &factorization);
  return factorization;
}
void Divisors(const unordered_map<long long int, int>& factorization,
              unordered_map<long long int, int>::iterator it,
              long long int divisor, vector<long long int>* result) {
  if (it == factorization.end()) {
    result->push_back(divisor);
    return;
  }
  for (int i = 0; i <= it->second; i++) {
    Divisors(factorization, next(it), divisor, result);
    divisor *= it->first;
  }
}
vector<long long int> Divisors(long long int n, const vector<int>& primes,
                               const vector<int>& factors) {
  unordered_map<long long int, int> factorization =
      Factorize(n, primes, factors);
  vector<long long int> divisors;
  Divisors(factorization, factorization.begin(), 1LL, &divisors);
  return divisors;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  vector<int> primes, factors;
  Sieve(FACTORS_THRESHOLD, &primes, &factors);
  int n, k;
  cin >> n >> k;
  for (int i = 0; i < n; i++) {
    cin >> T[i];
    A[T[i]]++;
  }
  long long int result = 0;
  for (int i = 1;; i++) {
    long long int pwr = Power(i, k);
    if (pwr >= INFLL) break;
    vector<long long int> dvs = Divisors(pwr, primes, factors);
    for (long long int x : dvs) {
      long long int y = pwr / x;
      if (x >= MAXN) continue;
      if (y >= MAXN) continue;
      if (x > y) continue;
      if (x != y) result += (long long int)A[x] * A[y];
      if (x == y) result += ((long long int)A[x] * (A[x] - 1)) / 2;
    }
  }
  cout << result << "\n";
  return 0;
}
