Suppose you are performing the following algorithm. There is an array v_1, v_2, ..., v_n filled with zeroes at start. The following operation is applied to the array several times — at i-th step (0-indexed) you can: 

  * either choose position pos (1 ≤ pos ≤ n) and increase v_{pos} by k^i; 
  * or not choose any position and skip this step. 



You can choose how the algorithm would behave on each step and when to stop it. The question is: can you make array v equal to the given array a (v_j = a_j for each j) after some step?

Input

The first line contains one integer T (1 ≤ T ≤ 1000) — the number of test cases. Next 2T lines contain test cases — two lines per test case.

The first line of each test case contains two integers n and k (1 ≤ n ≤ 30, 2 ≤ k ≤ 100) — the size of arrays v and a and value k used in the algorithm.

The second line contains n integers a_1, a_2, ..., a_n (0 ≤ a_i ≤ 10^{16}) — the array you'd like to achieve.

Output

For each test case print YES (case insensitive) if you can achieve the array a after some step or NO (case insensitive) otherwise.

Example

Input


5
4 100
0 0 0 0
1 2
1
3 4
1 4 1
3 2
0 1 3
3 9
0 59049 810


Output


YES
YES
NO
NO
YES

Note

In the first test case, you can stop the algorithm before the 0-th step, or don't choose any position several times and stop the algorithm.

In the second test case, you can add k^0 to v_1 and stop the algorithm.

In the third test case, you can't make two 1 in the array v.

In the fifth test case, you can skip 9^0 and 9^1, then add 9^2 and 9^3 to v_3, skip 9^4 and finally, add 9^5 to v_2.
import java.io.*; 

import java.util.*;
import java.util.Map.Entry;


public class  Adding_Powers     
{ 
    
    static class FastReader 
    { 
        BufferedReader br; 
        StringTokenizer st; 
  
        public FastReader() 
        { 
            br = new BufferedReader(new
                     InputStreamReader(System.in)); 
        } 
  
        String next() 
        { 
            while (st == null || !st.hasMoreElements()) 
            { 
                try
                { 
                    st = new StringTokenizer(br.readLine()); 
                } 
                catch (IOException  e) 
                { 
                    e.printStackTrace(); 
                } 
            } 
            return st.nextToken(); 
        } 
  
        int nextInt() 
        { 
            return Integer.parseInt(next()); 
        } 
  
        long nextLong() 
        { 
            return Long.parseLong(next()); 
        } 
  
        double nextDouble() 
        { 
            return Double.parseDouble(next()); 
        } 
  
        String nextLine() 
        { 
            String str = ""; 
            try
            { 
                str = br.readLine(); 
            } 
            catch (IOException e) 
            { 
                e.printStackTrace(); 
            } 
            return str; 
        } 
    } 
    public static long changeme(long b,int i,int fin,long num)
    {
        return ((b>>i)|(b<<(fin-i)))&num;
    }
    static long power(long x, long y, long m)  
    { 
        if (y == 0) 
            return 1; 
          
        long p = power(x, y / 2, m) % m; 
        p = (p * p) % m; 
      
        if (y % 2 == 0) 
            return p%m; 
        else
            return (x * p) % m; 
    } 
    static long modInverse(long a,long m) 
    { 
        return power(a, m - 2, m);  
    } 
    static long gcd(long a,long b)  
    { 
        if (a == 0) 
            return b; 
        return gcd(b % a, a); 
    } 
    static int kFactors(long n,long k) 
    { 
        ArrayList<Long> P = new ArrayList<Long>(); 
      
        // Insert all 2's in list 
        while (n % 2 == 0) 
        { 
            P.add(2l); 
            n /= 2; 
        } 
        for (int i = 3; i * i <= n; i = i + 2) 
        { 
            while (n % i == 0) 
            { 
                n = n / i; 
                P.add((long)i); 
            } 
        } 
        if (n > 2) 
            P.add(n); 
        if (P.size() < k) 
        {  
            return 0; 
        } 
        else
        {
            return 1;
        }
    } 
    public static long giveme_count(long x,long k)
    {
        long count=0;

        if(x==1)
            return 0;

        while(x>1 && x%k==0)
        {
            x=x/k;
            count++;
        }

        return count;
    }
    public static void main(String[] args) 
    { 
        FastReader sc=new FastReader(); 
        PrintWriter pw=new PrintWriter(System.out);
        
        int t=sc.nextInt();

        m:while(t-->0)
        {
            int n=sc.nextInt();

            long k=sc.nextLong();
            HashSet<Long> used=new HashSet<>();

            String str[]=sc.nextLine().trim().split(" ");

            for(int i=0;i<n;i++)
            {
                long x=Long.parseLong(str[i]);

                if(x==0)
                    continue;

                
                    while(x>0)
                    {
                        long h=giveme_count(x,k);
                        if(used.contains(h))
                        {
                            pw.println("NO");
                            continue m;
                        }
                        used.add(h);
                        x=x-(long)Math.pow(k,h);
                    }
                    

                
            }
            
            pw.println("YES");
        }
        pw.flush();

        
    }

} 