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



public class AddingPowers {
	static class FastScanner 
	{ 
		BufferedReader br; 
		StringTokenizer st; 

		public FastScanner() 
		{ 
			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 void main(String[] args){
      FastScanner f=new FastScanner();
      int t=f.nextInt();
      while(t-->0) {
    	int n=f.nextInt();
    	long k=f.nextLong();
    	long freq[]=new long[10000];
    	long arr[]=new long[n];
    	int z=0;
    	for(int i=0;i<n;i++) {
    		arr[i]=f.nextLong();
    		if(arr[i]==0) z++;
    	}
    	Arrays.sort(arr);
    	boolean ans=true;
    	for(int i=0;i<n;i++) {
    		if(PowerArray(arr[i],k,freq)==false) {
    			ans=false;
    			break;
    		}
    	}
    	
    	if(z==n) {
    		System.out.println("YES");
    	}
    	else if(ans==false) {
    		System.out.println("NO");
    	}else {
    		System.out.println("YES");
    	}
    	
      }
}

static boolean PowerArray(long n, long k,long freq[]) 
{ 
  
    // Initializing the counter 
    int count = 0; 
  
    // Executing the while 
    // loop until K is 
    // greater than 0 
    while (n > 0)  
    { 
        if (n % k == 0)  
        { 
            n /= k; 
            count++; 
        } 
  
        // If K % N == 1, 
        // then the power array 
        // is incremented by 1 
        else if (n % k == 1) 
        { 
            n -= 1; 
            freq[count]++; 
  
            // Checking if any power is 
            // occurred more than once 
            if (freq[count] > 1) 
            { 
                return false; 
            } 
        } 
  
        // For any other value, the sum of 
        // powers cannot be added up to K 
        else
        { 
           return false; 
        } 
    } 
    
    return true;
}

//BRIAN KERNINGHAM TO CHECK NUMBER OF SET BITS
	//O(LOGn)
	static int setBits(int n) {
		int count=0;
		while(n>0) {
			n=n&(n-1);
			count++;
		}
		return count;
	}
	
	//0 based indexing
	static boolean KthBitSet(int n,int k) {
		int mask=1;
		mask=mask<<=k;
		if((mask&n)!=0) return true;
		else return false;
	}
}
