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.
/*
If you want to aim high, aim high
Don't let that studying and grades consume you
Just live life young
******************************
If I'm the sun, you're the moon
Because when I go up, you go down
*******************************
*/
import java.util.*;
import java.io.*;
import java.math.*;

   public class x1246B3
   {
      public static void main(String omkar[]) throws Exception
      {
         //BufferedReader infile = new BufferedReader(new FileReader("cowdate.in"));
         BufferedReader infile = new BufferedReader(new InputStreamReader(System.in));  
         StringTokenizer st = new StringTokenizer(infile.readLine());
         int N = Integer.parseInt(st.nextToken());
         int K = Integer.parseInt(st.nextToken());
         int[] arr = new int[N];
         st = new StringTokenizer(infile.readLine());
         for(int i=0; i < N; i++)
            arr[i] = Integer.parseInt(st.nextToken());
         //preprocess
         int[] primes = gen(100000);
         HashMap<String, Integer> map = new HashMap<String, Integer>();
         String[] hashes = new String[100001];
         for(int x: arr)
         {
            ArrayList<Integer> ls = new ArrayList<Integer>();
            int val = x;
            for(int i=2; i <= (int)(Math.sqrt(x)); i++)
               if(val%i == 0)
               {
                  int cnt = 0;
                  while(val%i == 0)
                  {
                     val /= i;
                     cnt++;
                  }
                  ls.add(i);
                  ls.add(cnt);
               }
            if(val > 1)
            {
               ls.add(val);
               ls.add(1);
            }
            //hash
            StringBuilder sb = new StringBuilder(":");
            for(int i=0; i < ls.size(); i += 2)
            {
               int p = ls.get(i);
               int v = ls.get(i+1);
               v %= K;
               if(v == 0)
                  continue;
               sb.append(p).append(":").append(v).append(":");
            }
            String key = sb.toString();
            if(!map.containsKey(key))
               map.put(key, 0);
            map.put(key, map.get(key)+1);
            hashes[x] = key;
         }
         long res = 0L;
         for(int x: arr)
         {
            ArrayList<Integer> ls = new ArrayList<Integer>();
            int val = x;
            for(int i=2; i <= (int)(Math.sqrt(x)); i++)
               if(val%i == 0)
               {
                  int cnt = 0;
                  while(val%i == 0)
                  {
                     val /= i;
                     cnt++;
                  }
                  ls.add(i);
                  ls.add(cnt);
               }
            if(val > 1)
            {
               ls.add(val);
               ls.add(1);
            }
            //hash
            StringBuilder sb = new StringBuilder(":");
            for(int i=0; i < ls.size(); i += 2)
            {
               int p = ls.get(i);
               int v = ls.get(i+1);
               v = (K-v%K)%K;
               if(v == 0)
                  continue;
               sb.append(p).append(":").append(v).append(":");
            }
            String key1 = sb.toString();
            String key2 = hashes[x];
            if(map.containsKey(key1))
            {
               if(key1.equals(key2))
                  res += (long)map.get(key1)*(map.get(key1)-1)/2;
               else
                  res += (long)map.get(key1)*map.get(key2);
               map.put(key1, 0);
            }
         }
         System.out.println(res);
      }
      public static int[] gen(int N)
      {
         int[] arr = new int[N+1];
         arr[2] = 1;
         int boof = 2;
         for(int i=3; i <= N; i+=2)
            if(isPrime(i))
               arr[i] = boof++;
         return arr;
      }
      public static boolean isPrime(long n) 
      {
          if(n < 2) return false;
          if(n == 2 || n == 3) return true;
          if(n%2 == 0 || n%3 == 0) return false;
          long sqrtN = (long)Math.sqrt(n)+1;
          for(long i = 6L; i <= sqrtN; i += 6) {
              if(n%(i-1) == 0 || n%(i+1) == 0) return false;
          }
          return true;
      }
   }