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.text.DecimalFormat;
import java.util.*;





public class Template {

	

	//static int cnt=0;
	static int max=0;
	static ArrayList<Integer> v=new ArrayList();
static Scanner sc=new Scanner(System.in);
	static BufferedReader br=new BufferedReader(new InputStreamReader(System.in)); 
	//static boolean p=false;
	
	static ArrayList<Long> h1;
	static ArrayList<Long> h2;
	static long[][] arr;
	static long sum=0;
	public static void main (String[] args) throws java.lang.Exception{
	//int t=sc.nextInt();
	long t=sc.nextLong();
	while(t-->0) {
		long n=sc.nextLong();
		long k=sc.nextLong();
		ArrayList<Long> arr=new ArrayList();
	Map<Long,Long> pws=new HashMap();
		boolean p=true;
		for(long i=0;i<n;i++) {
			long c=sc.nextLong();
			if(c==0) {
				continue;
			}
			while(c>0) {
				
	
	long maxp=(long)(Math.log(c)/(1.0*Math.log(k)));
	maxp++;
	//System.out.println(maxp);
	if(maxp>0) {
		while((long)Math.pow(k, maxp)>c) {
		
			maxp--;
			
		}
	c=(long) (c-(long)Math.pow(k, maxp));
	//System.out.println("maxp"+maxp+" "+Math.pow(k, maxp)+" "+c);
	//System.out.println(pws);
	long v=maxp;
	if( pws.containsKey(v)) {
		System.out.println("NO");
		p=false;
		break;
	}
	else {
	pws.put((long) maxp,(long) 0);
	}
	}
	if(c<k && c!=1 && c!=0) {
		System.out.println("NO");
		p=false;
		break;
	}
	if(c==1) {
		if(pws.containsKey((long)0)) {
			System.out.println("NO");
			p=false;
			break;
		}
		else {
			pws.put((long)0, (long)0);
		
		break;
	}
			}
			
			}
			
			if(!p) {
				for(int j=(int) (i+1);j<n;j++) {
					sc.nextLong();
				}
				break;
			}
	
			
		
		
		
		}
			if(p) {
				
		//	System.out.println(pws);
				System.out.println("YES");
			}
	}
}	
/*
ArrayList<Long> ar=arrInpLong((int)n);
if(k==n) {
	System.out.println(0);
	return;
}
else if(k==1) {
	System.out.println(ar.get((int)n-1)-ar.get(0));
	return;
}
long diff=Long.MAX_VALUE;
long q=n/k;
//long rem=n%k;
ArrayList<Integer> index=new ArrayList();
for(long i=0;i<n-1;i=i+q) {
	index.add((int)i);
}
index.add((int)n-1);
for(int i=index.size()-2;i>0;i--) {
	int cindex=index.get(i);
	int pindex=index.get(i-1);
	int nindex=index.get(i+1);
	
		long init=ar.get(nindex)-ar.get(pindex+1);
		boolean exe=false;
				for(int trmp=pindex;trmp<nindex;trmp++) {
					if(ar.get(trmp)-ar.get(pindex)+ar.get(nindex)-ar.get(trmp+1)<=init) {
						
						init=ar.get(trmp)-ar.get(pindex)+ar.get(nindex)-ar.get(trmp+1);
						if(!exe && trmp==nindex-1) {
						index.set(i,(int)trmp);
						//sum+=init;
						}
						continue;
					}
					else {
						exe=true;
						trmp--;
						System.out.println(trmp);
               index.set(i, (int) trmp);
               
               System.out.println(ar.get(index.get(i+1))-ar.get(trmp+1));
						//sum+=ar.get(index.get(i+1))-ar.get(trmp+1);
			break;
					
				}
					
					

				
				}
				
}
System.out.println(index);
for(int j=0;j<index.size();j=j+2) {
	try {
		sum+=ar.get(index.get(j+1))-ar.get(index.get(j));
	}
	catch(Exception e) {
		
	}
}

System.out.println(sum);
	}
	/*if(op>cl && s.charAt(0)!=')') {
		int diff=op-cl;
		//if(open.containsKey(diff)) {
			//open.put(diff, open.get(diff)+1);
		//}
		//else {
			//open.put(diff,1);
			
		//}
		System.out.println(n);
		ar.add(diff);
	}
	
	else if(cl>op && s.charAt(s.length()-1)!='(') {
		
		int diff=cl-op;
		if(close.containsKey(diff)) {
			close.put(diff, close.get(diff)+1);
		}
		else {
			close.put(diff,1);
			
		}
		System.out.println(n);
		
	}
	else if(cl==op && s.charAt(0)!=')' && s.charAt(s.length()-1)!='('){
		count++;
	}
	
	
	


count=count/2;
	//System.out.println(ar);
	//System.out.println(close);
	//System.out.println(count);
	for(int i=0;i<ar.size();i++) {
		if(close.containsKey(ar.get(i))) {
			if(close.get(ar.get(i))>=1) {
				close.put(ar.get(i),close.get(ar.get(i))-1);
				count++;
			}
		}
	}
		
		System.out.println(count);



	}
	
	
	
	*/
		
	
	
	
	
	
	public static long fact(long i) {
	long fact=1;
		for(int j=2;j<=i;j++) {
			fact=fact*j;
		}
		return fact;
	}
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	public static void printArrInt(ArrayList<Integer> arr) {
		for(int i=0;i<arr.size();i++) {
			System.out.print(arr.get(i)+" ");
	}	
		}
	
	public static int[][] matrixInp(int n,int m) {
		int[][] arr=new int[n][m];
		for(int i=0;i<n;i++) {
			for(int j=0;j<m;j++) {
				arr[i][j]=sc.nextInt();
			}
		}
		return arr;
	}
	
	
	
	
	
	
	public static int bSearch(ArrayList<Long> arr,long n) {
		
		int start=0;
		int end=arr.size()-1;
		int mid=0;
		while(end>=start) {
		mid=start+(end-start)/2;
		if(arr.get(mid)==n) {
			break;
			
		}
		else if(arr.get(mid)>n) {
			end=mid-1;
		}
		else if(arr.get(mid)<n) {
			start=mid+1;
		}
		}
		return mid;
	}
	

	
	public static int reduceFraction(int a, int b)
	{
		int aa=a;
		if(a==0 || b==0)
			return Math.max(a, b);
		else {
			for(int i=2;i<=Math.min(a, b);i++) {
				if(a%i==0 && b%i==0) {
					a=a/i;
					b=b/i;
					i--;
				}
			}
			
			
		}
		
		return aa/a;
	}
	
	public static long sumDigits(long x) {
		String s=String.valueOf(x);
		//System.out.println(s+" "+sx+" "+x);
		long sum=0;
		for(int i=0;i<s.length();i++) {
			sum+=Long.parseLong(s.substring(i,i+1));
		}
		return sum;
	}
	
	
	public static int[] primeFactofNumb(int num) {
		int[] factors=new int[num+1];
		for(int j=2;j<=Math.sqrt(num);j++) {
			if(num%j==0) {
				factors[j]++;
			}
			while(num%j==0) {
				num=num/j;
			}
			
		}
		
		if(num>1)
			factors[num]++;
		return factors;
	}
	
	
	
	
	public static long nCr(int n, int k){ 
		long C[][] = new long[n + 1][k + 1];
        long i, j;
 
        // Calculate  value of Binomial
        // Coefficient in bottom up manner
        for (i = 0; i <= n; i++) {
            for (j = 0; j <= (long)Math.min(i, k); j++) {
                // Base Cases
                if (j == 0 || j == i)
                    C[(int) i][(int) j] = 1;
 
                // Calculate value using
                // previously stored values
                else
                    C[(int) i][(int) j] = C[(int) (i - 1)][(int) (j - 1)] + C[(int) (i - 1)][(int) j];
            }
        }
 
        return C[n][k];
	}
		
	
		
	

	
	
	

		
	
	
	
	
static long gcd(long a,long b) {
		
	
		if(b==0) {
		return a;
		}
		else if(a==0)
			return b;
			
		
	return gcd(b,a%b);
	
	}
	
	
	
	
	
	public static int s2i(String s) {
		return Integer.parseInt(s);
	}
	

	
	
	public static int LeastIntFn(int a,int b) {
		if((b%a)==0) {
			return (int)b/a;
		}
		return (int)(b/a)+1;
	}
	
	
	
	public static ArrayList<Long> arrInpLong(long n){
		ArrayList<Long> arr=new ArrayList();
		for(long i=0;i<n;i++) {
		arr.add(sc.nextLong());	
		}
		return arr;
	}
	public static ArrayList<String> arrInpStr(int n){
		ArrayList<String> arr=new ArrayList();
		for(int i=0;i<n;i++) {
					arr.add(sc.nextLine());	
		}
		return arr;
	}
	
	public static ArrayList<Integer> arrInpInt(int n){
		ArrayList<Integer> arr=new ArrayList();
		for(int i=0;i<n;i++) {
			int k=sc.nextInt();
			if(k>max)
				max=k;
		arr.add(k);	
		}
		return arr;
	}
	
	

	
	
	public static int min(int a,int b,int c) {
		int min1=Math.min(a, b);
		return Math.min(min1,c);
	}
}