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.
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.io.FilterInputStream;
import java.io.BufferedInputStream;
import java.io.InputStream;

/**
 * @author khokharnikunj8
 */

public class Main {
    public static void main(String[] args) {
        new Thread(null, new Runnable() {
            public void run() {
                new Main().solve();
            }
        }, "1", 1 << 26).start();
    }

    void solve() {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        ScanReader in = new ScanReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        BPowerProducts solver = new BPowerProducts();
        solver.solve(1, in, out);
        out.close();
    }

    static class BPowerProducts {
        int findMinNumber(int n) {
            int count = 0, ans = 1;
            while (n % 2 == 0) {
                count++;
                n /= 2;
            }
            if (count % 2 == 1)
                ans *= 2;
            for (int i = 3; i * i <= (n); i += 2) {
                count = 0;
                while (n % i == 0) {
                    count++;
                    n /= i;
                }
                if (count % 2 == 1)
                    ans *= i;
            }

            if (n > 2)
                ans *= n;
            return ans;
        }

        public void solve(int testNumber, ScanReader in, PrintWriter out) {
            int n = in.scanInt();
            int k = in.scanInt();
            int[] ar = new int[n];
            long ans = 0;
            long[] hash = new long[100005];
            for (int i = 0; i < n; i++) {
                ar[i] = in.scanInt();
                hash[ar[i]]++;
            }

            long[] answer = new long[100001];
            if (k == 2) {
                long[] div = new long[100001];
                for (int i = 1; i <= 100000; i++) {
                    int temp = findMinNumber(i);
                    ans += (hash[i] * (hash[i] - 1l)) / 2;
                    ans += (hash[i] * div[temp]);
                    div[temp] += hash[i];
                }
                out.println(ans);
                return;
            }
            out:
            for (int i = 1; i <= 100000; i++) {
                long power = i;
                for (int j = 0; j < k - 1; j++) {
                    power *= i;
                    if (power > 10000000000l) break out;
                }
                for (int j = 1; j <= power / j; j++) {
                    if (power % j == 0 && j <= 100000 && power / j <= 100000) {
                        if (j == power / j) answer[i] += (hash[j] * (hash[j] - 1)) / 2;
                        else answer[i] += (hash[j] * hash[(int) (power / j)]);
                    }
                }
            }
            for (int i = 100000; i >= 1; i--) {
                for (int j = 2 * i; j <= 100000; j += i) answer[j] -= answer[i];
                ans += answer[i];
            }
            out.println(ans);


        }

    }

    static class ScanReader {
        private byte[] buf = new byte[4 * 1024];
        private int index;
        private BufferedInputStream in;
        private int total;

        public ScanReader(InputStream inputStream) {
            in = new BufferedInputStream(inputStream);
        }

        private int scan() {
            if (index >= total) {
                index = 0;
                try {
                    total = in.read(buf);
                } catch (Exception e) {
                    e.printStackTrace();
                }
                if (total <= 0) return -1;
            }
            return buf[index++];
        }

        public int scanInt() {
            int integer = 0;
            int n = scan();
            while (isWhiteSpace(n)) n = scan();
            int neg = 1;
            if (n == '-') {
                neg = -1;
                n = scan();
            }
            while (!isWhiteSpace(n)) {
                if (n >= '0' && n <= '9') {
                    integer *= 10;
                    integer += n - '0';
                    n = scan();
                }
            }
            return neg * integer;
        }

        private boolean isWhiteSpace(int n) {
            if (n == ' ' || n == '\n' || n == '\r' || n == '\t' || n == -1) return true;
            else return false;
        }

    }
}

