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.BufferedWriter;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStreamWriter;


import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map.Entry;
import java.util.Random;
import java.util.TreeSet;

public final class CF_596_D1_B
{


	static boolean verb=true;
	static void log(Object X){if (verb) System.err.println(X);}
	static void log(Object[] X){if (verb) {for (Object U:X) System.err.print(U+" ");System.err.println("");}}
	static void log(int[] X){if (verb) {for (int U:X) System.err.print(U+" ");System.err.println("");}}
	static void log(int[] X,int L){if (verb) {for (int i=0;i<L;i++) System.err.print(X[i]+" ");System.err.println("");}}
	static void log(long[] X){if (verb) {for (long U:X) System.err.print(U+" ");System.err.println("");}}

	static void logWln(Object X){if (verb) System.err.print(X);}
	static void info(Object o){	System.out.println(o);}
	static void output(Object o){outputWln(""+o+"\n");	}
	static void outputWln(Object o){try {out.write(""+ o);} catch (Exception e) {}}

	static class Composite implements Comparable<Composite>{
		int v;
		int idx;
		public int compareTo(Composite X) {
			if (v!=X.v)
				return v-X.v;
			return idx-X.idx;
		}
		public Composite(int v, int idx) {
			this.v = v;
			this.idx = idx;
		}



	}

	static long mod=1000000007;

	// Global vars
	static BufferedWriter out;
	static InputReader reader;


	static void test() {
		log("testing");
		int NMAX=100;
		int NTESTS=10000;
		Random r=new Random();
		for (int t=0;t<NTESTS;t++) {
			int[] a=new int[NMAX];
			
		}
		log("done");

	}

	
	
	static long solveBourrin(int[] a,int k) {
		int n=a.length;
		long ans=0;
		for (int i=0;i<n;i++)
			for (int j=i+1;j<n;j++) {
				long m=a[i];
				m*=a[j];
				for (int x=1;x<=m;x++) {
					long xx=1;
					boolean ok=true;
					for (int u=0;u<k && ok;u++) {
						if (xx*x<=m) {
							xx*=x;
						} else {
							ok=false;
						}
					}
					if (ok && xx==m) {
						ans++;
					}
				}
			}
		
		return ans;
	}
	
	static long solveSubtil(int[] a,int k) {
		int n=a.length;
		ArrayList<Integer> primes=new ArrayList<Integer>();
		int MX=100001;
		int[] mem=new int[MX];
		for (int u=2;u<MX;u++) {
			if (mem[u]==0) {
				int v=u;
				primes.add(u);
				while (v<MX) {
					if (mem[v]==0) {
						mem[v]=u;
					}
					v+=u;
				}
			}
		}

		//ArrayList<Integer>[] lst=new ArrayList[n];
		HashMap<String,Integer> hm=new HashMap<String,Integer>();
		long ans=0;
		for (int i=0;i<n;i++) {
			
			//lst[i]=new ArrayList<Integer>();
			int u=a[i];
			String s="";
			String cm="";
			while (mem[u]>0) {
				int p=mem[u];
				int cnt=0;
				while (u%p==0) {
					u/=p;
					cnt+=1;
				}
				if (cnt%k!=0) {
					s+=p+"#"+(cnt%k)+":";
					//lst[i].add(p);
					//lst[i].add(cnt%k);
					cm+=p+"#"+(k-cnt%k)+":";
					
				}
			}
			//log(a[i]+" "+s+" // "+cm);
			Integer prev=hm.get(cm);
			if (prev!=null) {
				ans+=prev;
			}
			Integer z=hm.get(s);
			if (z==null)
				z=0;
			hm.put(s,z+1);
		}
		return ans;
	}


	static void process() throws Exception {


		out = new BufferedWriter(new OutputStreamWriter(System.out));
		reader = new InputReader(System.in);


		int n=reader.readInt();
		int k=reader.readInt();
		int[] a=new int[n];

		for (int i=0;i<n;i++)
			a[i]=reader.readInt();

		output(solveSubtil(a,k));
		
		try {
			out.close();
		} catch (Exception e) {
		}

	}
	
	
	

	public static void main(String[] args) throws Exception {
		process();

	}

	static final class InputReader {
		private final InputStream stream;
		private final byte[] buf = new byte[1024];
		private int curChar;
		private int numChars;

		public InputReader(InputStream stream) {
			this.stream = stream;
		}

		private int read() throws IOException {
			if (curChar >= numChars) {
				curChar = 0;
				numChars = stream.read(buf);
				if (numChars <= 0) {
					return -1;
				}
			}
			return buf[curChar++];
		}

		public final String readString() throws IOException {
			int c = read();
			while (isSpaceChar(c)) {
				c = read();
			}
			StringBuilder res = new StringBuilder();
			do {
				res.append((char) c);
				c = read();
			} while (!isSpaceChar(c));
			return res.toString();
		}

		public final int readInt() throws IOException {
			int c = read();
			boolean neg = false;
			while (isSpaceChar(c)) {
				c = read();
			}
			char d = (char) c;
			// log("d:"+d);
			if (d == '-') {
				neg = true;
				c = read();
			}
			int res = 0;
			do {
				res *= 10;
				res += c - '0';
				c = read();
			} while (!isSpaceChar(c));
			// log("res:"+res);
			if (neg)
				return -res;
			return res;

		}

		public final long readLong() throws IOException {
			int c = read();
			boolean neg = false;
			while (isSpaceChar(c)) {
				c = read();
			}
			char d = (char) c;
			// log("d:"+d);
			if (d == '-') {
				neg = true;
				c = read();
			}
			long res = 0;
			do {
				res *= 10;
				res += c - '0';
				c = read();
			} while (!isSpaceChar(c));
			// log("res:"+res);
			if (neg)
				return -res;
			return res;

		}

		private boolean isSpaceChar(int c) {
			return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
		}
	}

}