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.BufferedOutputStream;
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.FileOutputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintStream;
import java.util.Locale;
import java.util.StringTokenizer;

public class Solution implements Runnable {
	
	public static final int MAXA = 100000;
	
	private PrintStream out;
	private BufferedReader in;
	private StringTokenizer st;
	
	public void solve() throws IOException {
		long time0 = System.currentTimeMillis();
		
		int n = nextInt();
		int k = nextInt();
		int[] a = new int[n];
		for (int i = 0; i < n; i++) {
			a[i] = nextInt();
		}
		
		long answer = solve(n, k, a);
		out.println(answer);
		
		System.err.println("time: " + (System.currentTimeMillis() - time0));
	}
	
	private long solve(int n, int k, int[] a) {
		long[] primesK = calcPrimesK(k);
		long result = 0;
		int[] aps = new int[MAXA + 1];
		for (int i = 0; i < n; i++) {
			Decomposition d = new Decomposition(a[i], k, primesK);
			if (d.invalid()) {
				continue;
			}
			result = result + aps[d.co];
			aps[d.re] += 1;
		}
		return result;
	}
	
	private long[] calcPrimesK(int k) {
		long[] result = new long[MAXA + 1];
		result[0] = -1;
		result[1] = 1;
		for (int i = 2; i < result.length; i++) {
			if (result[i] == -1) {
				continue;
			}
			for (int j = 2; 1L * i * j < result.length; j++) {
				result[i * j] = -1;
			}
			result[i] = pow(i, k);
		}
		return result;
	}

	private long pow(int i, int k) {
		if (k == 0) {
			return 1;
		}
		long result = 1;
		if (k % 2 == 1) {
			result = i;
		}
		long mult = pow(i, k / 2);
		if (mult == -1 || mult > MAXA) {
			return -1;
		}
		result = result * mult;
		if (result > 1L * MAXA * MAXA) {
			return -1;
		}
		result = result * mult;
		if (result > 1L * MAXA * MAXA) {
			return -1;
		}
		return result;
	}

	private static final class Decomposition {
		private int re;
		private int co;
		private Decomposition(int x, int k, long[] primesK) {
			re = 1;
			co = 1;
			for (int i = 2; 1L * i * i <= x; i++) {
				int cnt = 0;
				while (x % i == 0) {
					x = x / i;
					cnt++;
				}
				cnt %= k;
				if (cnt > 0) {
					if (primesK[i] == -1) {
						re = -1;
						co = -1;
						return;
					}
					int readd = 1;
					for (int j = 0; j < cnt; j++) {
						readd *= i;
					}
					re *= readd;
					long coadd = primesK[i] / readd;
					if (coadd > MAXA || co * coadd > MAXA) {
						re = -1;
						co = -1;
						return;
					}
					co = co * (int) coadd;
				}
			}
			if (x > 1) {
				int i = x;
				int cnt = 0;
				while (x % i == 0) {
					x = x / i;
					cnt++;
				}
				cnt %= k;
				if (cnt > 0) {
					if (primesK[i] == -1) {
						re = -1;
						co = -1;
						return;
					}
					int readd = 1;
					for (int j = 0; j < cnt; j++) {
						readd *= i;
					}
					re *= readd;
					long coadd = primesK[i] / readd;
					if (coadd > MAXA || co * coadd > MAXA) {
						re = -1;
						co = -1;
						return;
					}
					co = co * (int) coadd;
				}
			}
		}
		private boolean invalid() {
			return re == -1;
		}
		public String toString() {
			return "{" + re + ", " + co + "}";
		}
	}

	public double nextDouble() throws IOException {
		return Double.parseDouble(next());
	}
	
	public long nextLong() throws IOException {
		return Long.parseLong(next());
	}
	
	public int nextInt() throws IOException {
		return Integer.parseInt(next());
	}
	
	public String next() throws IOException {
		while (!st.hasMoreTokens()) {
			String line = in.readLine();
			if (line == null) {
				return null;
			}
			st = new StringTokenizer(line);
		}
		return st.nextToken();
	}
	
	@Override
	public void run() {
		try {
			solve();
			out.close();
		} catch (Throwable e) {
			throw new RuntimeException(e);
		}
	}
	
	public Solution(String name) throws IOException {
		Locale.setDefault(Locale.US);
		if (name == null) {
			in = new BufferedReader(new InputStreamReader(System.in));
			out = new PrintStream(new BufferedOutputStream(System.out));
		} else {
			in = new BufferedReader(new InputStreamReader(new FileInputStream(name + ".in")));
			out = new PrintStream(new BufferedOutputStream(new FileOutputStream(name + ".out")));
		}
		st = new StringTokenizer("");
	}
	
	public static void main(String[] args) throws IOException {
		new Thread(new Solution(null)).start();
	}
}
