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.math.BigInteger;
import java.util.*;
import java.lang.*;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
import java.util.stream.Stream;

public class Contest {
	//static ArrayList<Integer> prime=new ArrayList();
	
	   public static TreeMap<Long,Integer> t1=new TreeMap();
	    public static void solve()
	    {
	      long m=1;
	      for(int j=2;j<=1000;j++)
	      {
	         
	          if(isprime(j))
	          {
	              m=m*j;
	              if(m>1000000)
	              {
	                  break;
	              }else{
	                  t1.put(m,1);
	              }
	          }
	      }
	    }
	public static long gcd(long n1, long n2)
    {
        if (n2 != 0)
            return gcd(n2, n1 % n2);
        else
            return n1;
    }
	
//////////////////	
	public static class trie {
        int x,y,z;
        trie (int x,int y,int z){
            this.x=x;
            this.y=y;
            this.z=z;
        }
	
	} 
        
	public static class pair {
        int x,y;
        pair (int x,int y){
            this.x=x;
            this.y=y;
        }
        public boolean equals(Object o) {
        	if(o instanceof pair) {
        		pair p = (pair)o;
        		return (x == p.x && y == p.y);
        	}
        	return false;
        }
        public int hashCode() {
        	return (Integer.hashCode(x) * 3 + Integer.hashCode(y) );
        }
    }
	
//////////////////	
	
	static class Cmp implements Comparator<pair>
	{
		public int compare(pair a,pair b)
		{
			if(a.x==b.x)
			{
				return(a.y-b.y);
			}
			return(a.x-b.x);
		}
	}
	
	
//////////////////
	
	
	
	
//////////////////
	
	
	
	
	
	   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 ArrayList<Integer> a=new ArrayList();
	   
	  public static ArrayList<Integer> Divisors(int n) 
	   { 
	       // Note that this loop runs till square root 
		  ArrayList<Integer> a=new ArrayList();
		   long sum=0;
	       for (int i=1; i*i<=(n); i++) 
	       { 
	           if (n%i == 0) 
	           { 
	               // If divisors are equal, print only one 
	               if (n/i == i) 
	               {
	                  // printf("%d ", i); 
	            	   sum=sum+1;
	            	   a.add(i);
	               }
	     
	               else // Otherwise print both 
	               {
	                   //printf("%d %d ", i, n/i); 
	            	   sum=sum+2;
	            	   a.add(i);
	            	   a.add(n/i);
	               }
	           } 
	       } 
	       return(a);
	   } 
	   
/////////////////////	  
	  
	  public static long SmallestPrimeDivisor(long n) 
	  { 
	      // if divisible by 2 
	      if (n % 2 == 0) 
	          return 2; 
	    
	      // iterate from 3 to sqrt(n) 
	      for (long i = 3; i * i <= n; i += 2) { 
	          if (n % i == 0) 
	              return i; 
	      } 
	    
	      return n; 
	  } 
	    
////////////////////	  
	   
	   public static boolean isprime(long n)
	    {
	        int count=0;
	     
	        for(long i=2;i*i<=n;i++)
	        {
	            if(n%i==0)
	            {
	                return(false);
	            }
	        }
	        return(true);
	    }
	
	   
//////////////////////
	   
	     //   (x^n)%1000000007
	   public static long modularExponentiation(long x,long n,long M)
	   {
	       if(n==0)
	           return 1;
	       else if(n%2 == 0)        //n is even
	           return modularExponentiation((x*x)%M,n/2,M);
	       else                             //n is odd
	           return (x*modularExponentiation((x*x)%M,(n-1)/2,M))%M;

	   }
	   
	   public static long nCr(int n,int k)
	   {
		  if(k==0)
			  return 1;
		  return(n*nCr(n-1,k-1)/k);
	   }
	   public static long factorial(int n)
	   {
		   if(n==1)
			   return 1;
		   return((n)*factorial(n-1));
	   }
	   
	   public static void debug(Object...o) {
		    System.out.println( Arrays.deepToString(o) );
	   }
	   
	   public static boolean prime[]=new boolean[100005];
	   //prime[j]==false means it's a prime.
	   public static void seive()
	   {
		   prime[0]=false;
		   prime[1]=false;
		   for(int i=2;i*i<=100005;i++)
		   {
			   if(!prime[i])
			   {
				   for(int j=i*i;i<=100005;j+=i)
				   {
					   prime[j]=true;
				   }
			   }
		   }
	   }
	    public static long AtMost(int k,char c[])
	    {
	    	long ans=0;
	    	int left=0,right=0;
	    	int n=c.length;
	    	HashMap<Character,Integer> h=new HashMap();
	    	h.put('1',0);
	    	while(right<n)
	    	{
	    		h.put(c[right],h.getOrDefault(c[right],0)+1);
	    		while(h.get('1')>k)
	    		{
	    			h.replace(c[left],h.get(c[left])-1);
	    			left++;
	    		}
	    		ans=ans+(right-left+1);
	    		right++;
	    	}
	    	return ans;
	    }
	 
	 
	    public static boolean equals(StringBuilder sb1, StringBuilder sb2){
	        
	        /*
	         * If both refer to the same object, they are equal
	         */
	        if(sb1 == sb2)
	            return true;
	 
	        /*
	         * If any of them is null, then they are not equal.
	         * We know both are not null at this point because of the previous
	         * condition which checks equality.
	         */
	        if(sb1 == null || sb2 == null)
	            return false;
	        
	        boolean isEqual = true;
	        
	        /*
	         * If both are not same length, they are not equal
	         */
	        if(sb1.length() == sb2.length()){
	            
	            /*
	             * Now, compare the characters one by one, and break the loop
	             * as soon as the characters at given position are different.
	             */
	            for(int i = 0 ; i < sb1.length(); i++){
	                
	                if(sb1.charAt(i) != sb2.charAt(i)){
	                    isEqual = false;
	                    break;
	                }
	            }
	            
	        }else{
	            isEqual = false;
	        }
	        
	        return isEqual;
	    }
	
	   
	   
	   
	   

		public static void main(String []args) throws Exception
		{
			
			
			 FastReader in =new FastReader();	
			 PrintWriter pw = new PrintWriter(System.out);
		    //Scanner sc=new Scanner(System.in)
			int t=in.nextInt();
			while(t-->0)
			{
				int n=in.nextInt();
				int k=in.nextInt();
				String s[]=new String[n];
				Arrays.fill(s,"");
				int max=0;
				HashMap<String,Integer> h=new HashMap();
				long a[]=new long[n];
				for(int i=0;i<n;i++)
				{
					a[i]=in.nextLong();
					
				}	
				int ans=0;
				for(int i=0;i<n;i++)
				{
					long x=a[i];
					if(x==0)
					{
						s[i]="0";
					}
					while(x!=0)
					{
						long p=x%k;
						if(p>1)
						{
							ans=1;
							break;
						}
						s[i]=Long.toString(p)+s[i];
						x=x/k;
						if(x<k)
						{
							if(x>1)
							{
								ans=1;
								break;
							}
							s[i]=Long.toString(x)+s[i];
							break;
						}
					}
					if(ans==1)
					{
						break;
					}
					int m=s[i].length();
					if(m>max)
					{
						max=m;
					}
					Integer y=h.get(s[i]);
					if(y==null)
					{
						h.put(s[i],m);
					}
					
				}
				
				
				
				if(ans==1)
				{
					pw.println("NO");
				}
				else
				{
					for(int i=0;i<n;i++)
					{
						int m=h.get(s[i]);
						for(int j=0;j<max-m;j++)
						{
							s[i]="0"+s[i];
						}
					}
					/*
					for(int i=0;i<n;i++)
					{
						pw.println(s[i]);
					}
					*/
					for(int i=0;i<max;i++)
					{
						int one=0;
						for(int j=0;j<n;j++)
						{
							if(s[j].charAt(i)=='1')
							{
								one++;
							}
						}
						if(one>1)
						{
							ans=1;
							break;
						}
						
					}
					if(ans==0)
					{
						pw.println("YES");
					}
					else
					{
						pw.println("NO");
					}
				}
				
			}
						
			
			pw.flush();
			pw.close();
		   			
		}
			
	}	
		
		
		
		
		
		
		
		
		
		
	

