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.io.OutputStream;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.StringTokenizer;


public class C{
	
	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; 
        } 
    }
	
	static class Pair
    {
		int a;
		int b;
		
		Pair(int a,int b)
		{
			this.a = a;
			this.b = b;
		}
		
		public int hashCode(){
	        //System.out.println("In hashcode");
	        int hashcode = 0;
	        hashcode = a*20;
	        hashcode += b*20;
	        return hashcode;
	    }
	     
	    public boolean equals(Object obj){
	        //System.out.println("In equals");
	        if (obj instanceof Pair) {
	            Pair pp = (Pair) obj;
	            return (pp.a == this.a && pp.b == this.b);
	        } else {
	            return false;
	        }
	    
	}
    }
	
/*
	static class SegmentTree {
        public int[] seg;
        public int N;
        public int size;

        public SegmentTree(int n) {
            
        	int h = (int)Math.ceil((double)Math.log(n)/Math.log(2));
        	
        	this.size = (int)Math.pow(2,h)*2-1;
        	seg = new int[size];
        }



        public int update(int l, int r, int i, int val) {
        	
        	
        	if(l == r && l == val)
        	{
        		seg[i]++;
        		return seg[i];
        	}
        	if(l > r || l == r || val > r || val < l) return seg[i];
            int m = (l+r) >>> 1;
            
            int left = update(l,m,2*i+1,val);
            
            int right = update(m+1,r,2*i+2,val);
            
            seg[i] = left+right;
            return seg[i];
        }

        

        public int getValue(int l, int r, int i, int ql, int qr) {
        	
            if (l > r || ql > qr || l > qr || r < ql) return 0;
            if (l == r) {
                return seg[i];
            }
            if (l >= ql && r <= qr) {
                return seg[i];
            }
            int m = (l + r) >>> 1;
            return getValue(l, m, 2 * i + 1, ql, qr) + getValue(m + 1, r, 2 * i + 2, ql, qr);
        }

    }
	
	public static int gcd(int a,int b)
	{
		if(a == 0) return b;
		if(b == 0) return a;
		
		return gcd(b, a%b);
	}
*/





	static LinkedList<Edge> gr[];
	static int n;
	
	static class Edge implements Comparable<Edge>
	{ 
		int u;
		int v;
		long p =1;
		
		Edge(int u,int v)
		{
			this.u = u;
			this.v = v;
		}
		
		public int compareTo(Edge o) 
		{
			
				if(p > o.p) return 1;    //increasing order
				else return -1;
		}
	}
	
	static Edge ed[];
	
	static int j = 0;
	static int dfs(int x,int p)
	{	
		int count = 0;
		for(Edge e:gr[x])
		{	
			
			if(e.v == p) continue;
			int cnt = dfs(e.v,x);
			count += cnt;
			e.p = (long)cnt*(n-cnt);
			
			ed[j++] = e;
		}
		count += 1;
		return count;
	}
	
	public static void main(String[] args) 
	{
		OutputStream outputStream = System.out;
        FastReader sc = new FastReader();
        PrintWriter out = new PrintWriter(outputStream);
        
        int t = sc.nextInt();
        
        outer: while(t-- > 0)
        {
        	int n = sc.nextInt();
        	int k = sc.nextInt();
        	
        	long a[] = new long[n];
        	
        	for(int i = 0; i < n; i++)
        	{
        		a[i] = sc.nextLong();
        	}
        	
        	PriorityQueue<Long> pq = new PriorityQueue<>(1,Collections.reverseOrder());
        	
        	for(int i = 0; i < n; i++)
        	{
        		if(a[i] != 0) 
        		{
        			pq.add(a[i]);
        		}
        	}
        	
        	long pow = Long.MAX_VALUE;
        	while(!pq.isEmpty())
        	{
        		long x = pq.poll();
        		
        		long di = (long) (Math.log(x)/Math.log(k));
        		
        		long r = di;
        		if((long)Math.pow(k,di+1) <= x && (long)Math.pow(k,di+1) > (long)Math.pow(k,di))
        		{
        			r = di+1;
        		}
        		if((long)Math.pow(k,di) > x)
        		{
        			r = di-1;
        		}
        		
        		if(r < pow)
        		{	
        			long cp = x;
        			x = x - (long)Math.pow(k, r);
        			//System.out.println(cp+" "+r+" "+x);
        			//if(x < 0) throw new RuntimeException();
        			if(x > 0) pq.add(x);
        			pow = r;
        		}
        		
        		else
        		{
        			out.println("NO");
        			continue outer;
        		}
        	}
        	
        	out.println("YES");
        	
        }
        
        out.close();
	}

}
