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.
// package CodeForces;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Scanner;
import java.util.Stack;
import java.util.StringTokenizer;

public class Solution1 {
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		FastReader s = new FastReader();
		int t = s.nextInt();
		StringBuilder str = new StringBuilder();
		for(int Case = 0 ; Case < t ; Case++) {
			 int n = s.nextInt();
			 long k = s.nextLong();
			 HashSet<Integer> set = new HashSet<>();
			 int flag = 0;
			 long[] arr = new long[n];
			 for(int i = 0 ; i < n ; i++) {
				 arr[i] = s.nextLong();
			 }
			 for(int i = 0 ; i < n ; i++) {
				 long ele = arr[i];
//				 System.out.println(ele);
				 if(ele == 0) continue;
				 else if(ele == 1 && !set.contains(0)) {
					 set.add(0);
				 }else if(ele < k ){
					 flag = 1;
					 break;
				 }else {
					 int pow = 0;
					 while(ele != 0){
						 while(ele % k == 0){
							 ele /= k;
							 pow++;
						 }
						 ele--;
						 if(set.contains(pow)) {
							 flag = 1;
							 break;
						 }
						 set.add(pow);
					 }
				 }
//				 System.out.println(set);
			 }
			 if(flag == 0)str.append("YES\n");
			 else str.append("NO\n");
			
		}
		System.out.println(str);
		
	}
	 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; 
	        } 
	    } 

}

//6
//1 1 1
//3 6 0
//0 0 0
//0 1 1
//10 1 10
//4 4 1
