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 cf;
import com.sun.security.jgss.GSSUtil;
import org.w3c.dom.html.HTMLBRElement;

import java.io.*;
import java.math.BigInteger;
import java.util.*;
import java.util.jar.JarOutputStream;

public class T_class {
    static int p=1000000007;
    static int max=(int)1e5;
    static boolean prime[]=new boolean[max];
    static  int dp[][][][]=new int[72][72][72][72];
   public static void main(String[] args) throws Exception{
        BufferedWriter out = new BufferedWriter(new OutputStreamWriter(new FileOutputStream(java.io.FileDescriptor.out), "ASCII"), 512);
        FastReader sc=new FastReader();
        int t=sc.nextInt();
        StringBuilder sb2=new StringBuilder();
        //
        // 12654
        while(t-- >0) {
            int n = sc.nextInt();
            long k=sc.nextLong();
            long ar[]= new long[n];
            boolean not=true;
            for(int i=0;i<n;i++)
            {
                ar[i]=sc.nextLong();
            }
            Arrays.sort(ar);
            for(int i=0;i<n/2;i++)
            {
                long temp=ar[i];
                ar[i]=ar[n-1-i];
                ar[i]=temp;
            }
            int end=(int)( Math.log10(1e16)/Math.log10(k));
            long pow[]= new long[end+1];
           // System.out.println(end);
            pow[0]=1;
            for(int i=1;i<=end;i++) {
            pow[i]=pow[i-1]*k;

            }
            Set<Integer> s=new HashSet<>();
            for(int i=0;i<n;i++)
            {
                long te=ar[i];
                if(te==0)
                    continue;
            for(int i1=end;i1>=0;i1--)
            {
                if(te>=pow[i1]&&s.contains(i1)==false)
                {
                    te-=pow[i1];
                    s.add(i1);
                }
            }
            if(te!=0)
            {
                not=false;
                break;
            }
            ar[i]=te;
            }
          //  System.out.println(f);
            if(not)
                sb2.append("YES");
            else
                sb2.append("NO");
                   sb2.append("\n");
            //System.out.println(set.size());
        }
           System.out.println(sb2.toString());
        out.flush();
    }
   /* static  boolean f=false;
    public  static boolean ans(long ar[],int n,long k,int shift)
    {
        int c=0;
       // System.out.println(Arrays.toString(ar));
        for(int i=0;i<n;i++) {
        if(ar[i]!=0)
            c++;
        }
       // System.out.println(c);
        if(c==0)
        {
            f=true;
           // System.out.println("done");
            return false;
        }
        if(shift>16)
        {
            return false;
        }

        //System.out.println(shift);
        for(int i=0;i<n&&!f;i++)
        {
            if(ar[i]==0)
                continue;
            else if(ar[i]-(pow[shift])>=0)
            {
                ar[i]-=pow[shift];
                ans(ar,n,k,shift+1);
                ar[i]+=(pow[shift]);
                ans(ar,n,k,shift+1);

            }
        }
        return false;
    }*/
    static  int ht[]=new int[max];
    static class BIT {
        long[] tree;
        public BIT(int size) {
            tree = new long[size + 1];
        }
        public long sum(int i) {
            long ans = 0;
            while (i > 0) {
                ans += tree[i];
                i -= i & -i;
            }
            return ans;
        }

        public long query(int i, int j) {
            return sum(j) - sum(i - 1);
        }

        public void add(int i, long val) {
            while (i < tree.length) {
                tree[i] += val;
                i += i & -i;
            }
        }

        public void set(int i, long val) {
            add(i, val - query(i, i));
        }
    }
    static class  vert implements Comparator<vert>
    {
        int v;
        TreeSet<Integer> set;

        public vert(int v, TreeSet<Integer> set) {
            this.v = v;
            this.set = set;
        }

        @Override
        public int compare(vert o1, vert o2) {
            return -(o1.set.size()-o2.set.size());
        }
    }
    public static long pow(long a,long b,long m)
    {
        long r=1;
        while(b!=1)
        {
            if(b%2!=0)
                r=(r*a)%m;
            b=b>>1;
            a=(a*a)%m;
        }
        return (r*a)%m;
    }
    public static long gcd(long a,long b)
    {
        if(b>a)
        {
            a=a^b;
            b=a^b;
            a=a^b;
        }
        if(b==0)
            return a;
        return gcd(b,a%b);
    }
    public static void extgcd(long a,long b)
    {/*
            if(a==0)
            {
                x=0;
                y=1;
                d=b;
                // return ;
            }
            else
            {

                extgcd(b%a,a);

                long t=y;
                y=x;
                x=t-(b/a)*x;
            }*/
    }
    public static void dfs(List<Integer> adj[],int u,int p)
    {
        ht[u]=ht[p]==1?2:1;
        for(int v:adj[u])
        {
            if(v!=p)
            {
                dfs(adj,v,u);
            }
        }
    }
    public static void seive()
    {
        for(int i=0;i<max;i++)
            prime[i] = true;

        for(int p = 2; p*p <=max; p++)
        {
            // If prime[p] is not changed, then it is a prime
            if(prime[p] == true)
            {
                // Update all multiples of p
                for(int i = p*p; i <=max; i += p)
                    prime[i] = false;
            }
        }

        // Print all prime numbers
        for(int i = 2; i <= max; i++)
        {
            if(prime[i] == true)
            {
               // l1.add(i);
            }
        }
    }
    public static boolean union(int a, int b, int p[], int r[]){
        // add your code here
        int pa=find(a,p,r);
        int pb=find(b,p,r);
        if(pa==pb)
            return true;
        if(pa!=pb)
        {
            if(r[pa]<r[pb])
            {
                p[pa]=pb;
            }
            else if(r[pa]>r[pb])
            {
                p[pb]=pa;
            }
            else
            {
                p[pa]=pb;
                r[pb]++;
            }
        }
        return false;
    }
    public static int find(int x,int p[],int r[])
    {
        if(p[x]==x)
            return x;
        p[x]=find(p[x],p,r);
        return p[x];
    }
    public static int binary_Search_upper(Integer[] ar, Integer x)
    {
        int res=-1;
        int l=0;int r=ar.length-1;
        while(l<=r)
        {
            int mid=(l+r)>>1;
            if(ar[mid]==x)
            {
                res=mid;
                l=mid+1;
            }
            else if(ar[mid]>x)
            {
                //res=mid;
                r=mid-1;
            }
            else
            {
                l=mid+1;
            }
        }
        return res;
    }
    public static int binary_Search_lower(int[] ar, int x,int l,int r)
    {
        int res=-1;
        //int l=0;int r=ar.length-1;
        while(l<=r)
        {
            int mid=(l+r)>>1;
            if(ar[mid]==x)
            {
                res=mid;
                r=mid-1;
            }
            else if(ar[mid]>x)
            {
                r=mid-1;
            }
            else
            {
          //      res=mid;
                l=mid+1;
            }
        }
        return res;
    } public static int binary_Search_lower_suf(int[] ar, int x,int l,int r)
    {
        int res=-1;
        //int l=0;int r=ar.length-1;
        while(l<=r)
        {
            int mid=(l+r)>>1;
            if(ar[mid]==x)
            {
                res=mid;
                r=mid-1;
            }
            else if(ar[mid]<x)
            {
                r=mid-1;
            }
            else
            {
                //      res=mid;
                l=mid+1;
            }
        }
        return res;
    }
    int bit[]=new int[(int)1e6];
    public void update(int n,int val,int i)
    {
        i++;
        while(i<n)
        {
            bit[i]+=val;
            i+=(i)&(-i);
        }

    }
    public long query(int n,int i)
    {
        i++;
        long sum=0;
        while(i>0)
        {
            sum+=bit[i];
            i-=(i)&(-i);
        }
        return sum;
    }


    ///////////////////////////////////////////////////////////////////////////////////
    //////////////////////////////////////////////////////////////////////////////////////////////
    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;
        }
    }


}
