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.util.*;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.BufferedReader;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class contest_1246_problem_B {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        TaskB solver = new TaskB();
        solver.solve(1, in, out);
        out.close();
    }

    static class TaskB {
        private Map<ArrayList, Integer> factorMap = new HashMap<>();

        public void solve(int testNumber, InputReader in, PrintWriter out) {
            int n = in.nextInt();
            int k = in.nextInt();
            int[] a = new int[n];
            int max = Integer.MIN_VALUE, min = Integer.MAX_VALUE;
            for (int i = 0; i < n; i++) {
                a[i] = in.nextInt();
                max = Math.max(max, a[i]);
                min = Math.min(min, a[i]);
            }
            int[] d = new int[max+1];
            for (int i = 1; i <= max; i++) {
                d[i] = i;
            }
            /** 将d[i]设置为i的最小质因子, 因为是从小到大的顺序，所以如果d[i]==i，就表示遇到了一个
             *  质数，
             * */
            for (int i = 2; i*i <= max; i++) {
                if (d[i] == i) {
                    for (int j = i; j * i <= max; j = j + 1) {
                        if(d[j*i]==j*i){
                            d[j*i] = i;
                        }
                    }
                }
            }
            long ret = 0;
            /**遍历每个数，生成质因子公式，根据公式取可配对的*/
            for (int i = 0; i < n; i++) {
                int x = a[i];
                int factorCount, factor;
                ArrayList<Integer> factorCountList = new ArrayList<>();
                ArrayList<Integer> factorCountPairList = new ArrayList<>();
                while (x > 1) {
                    factor = d[x];
                    factorCount = 0;
                    while(x%factor == 0){
                        x = x/factor;
                        factorCount++;
                    }
                    if(factorCount%k!=0){
                        factorCountList.add(factor);
                        factorCountList.add(factorCount%k);
                        factorCountPairList.add(factor);
                        factorCountPairList.add(k-factorCount%k);
                    }
                }
                if(factorMap.containsKey(factorCountPairList)){
//                    out.print(factorMap.get(factorCountPairList));
//                    out.println("-"+a[i]);
                    ret += factorMap.get(factorCountPairList);
                }
                if(factorMap.containsKey(factorCountList)){
                    factorMap.put(factorCountList, factorMap.get(factorCountList)+1);
                } else {
                    factorMap.put(factorCountList, 1);
                }

            }
            out.println(ret);
            return;
        }


    }

    static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

    }
}

