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.util.Arrays;
import java.util.TreeMap;
import java.util.TreeSet;

import static java.lang.Math.min;

public class Main
{
    boolean multiple = true;
    long MOD = 1000000007;

    @SuppressWarnings("Duplicates")
    void solve() throws Exception
    {
        int n = sc.nextInt();
        long k = sc.nextLong();
        long[] target = larr(n);
        boolean gay = true;
        for (int pow = 0; pow < 100; pow++)
        {
            boolean allZero = true;
            for (long l : target) allZero &= l == 0;
            if (allZero) break;
            int count = 0;
            for (long l : target)
                if (l % k == 1) count++;
                else if (l % k > 1) gay = false;
            if (count > 1) gay = false;
            for (int i = 0; i < n; i++) target[i] /= k;
        }
        System.out.println((gay) ? "YES" : "NO");
    }

    long inv(long a, long b) { return 1 < a ? b - inv(b % a, a) * b / a : 1; }
    long gcd(long a, long b) { return a == 0 ? b : gcd(b % a, a); }
    long powmod(long x, long pow) { if (pow == 0) return 1L;long temp = powmod(x,pow / 2);if (pow % 2 == 0) return (temp * temp) % MOD;return (((x * temp) % MOD) * temp) % MOD; }
    long lcm(long a, long b) { return (a * b) / gcd(a , b); }
    <T> void printarr(T[] arr) { for (T t : arr) System.out.print(t + " ");System.out.println(); }
    TreeMap<Integer, TreeSet<Integer>> buildGraph(int n, int m) throws Exception{TreeMap<Integer, TreeSet<Integer>> graph = new TreeMap<>();for (int i = 1; i <= n; i++) graph.put(i, new TreeSet<>());for (int i = 0; i < m; i++) { int u = sc.nextInt();int v = sc.nextInt();graph.get(u).add(v);graph.get(v).add(u); }return graph; }
    TreeMap<Integer, TreeSet<Integer>> buildDirGraph(int n, int m) throws Exception { TreeMap<Integer, TreeSet<Integer>> graph = new TreeMap<>();for (int i = 1; i <= n; i++) graph.put(i, new TreeSet<>());for (int i = 0; i < m; i++) graph.get(sc.nextInt()).add(sc.nextInt());return graph; }
    TreeMap<Integer, TreeSet<Integer>> revGraph(TreeMap<Integer, TreeSet<Integer>> graph) { TreeMap<Integer, TreeSet<Integer>> rev = new TreeMap<>();for (Integer u : graph.keySet()) rev.put(u, new TreeSet<>());for (Integer u : graph.keySet()) for (Integer v : graph.get(u)) rev.get(v).add(u);return rev; }
    int[] iarr(int n) throws Exception { int[] a = new int[n];for (int i = 0; i < n; i++) a[i] = sc.nextInt();return a; }
    Integer[] Iarr(int n) throws Exception { Integer[] a = new Integer[n];for (int i = 0; i < n; i++) a[i] = sc.nextInt();return a; }
    long[] larr(int n) throws Exception { long[] a = new long[n];for (int i = 0; i < n; i++) a[i] = sc.nextLong();return a; }
    TreeMap<Long, Integer> counts(long[] arr) { TreeMap<Long, Integer> counts = new TreeMap<>(); for (long a : arr) { if (!counts.containsKey(a)) counts.put(a, 0); counts.put(a, counts.get(a) + 1);} return counts; }
    String reverse(String s, int i, int j) /*[i, j] closed*/ { return (i > j) ? reverse(s, j, i) : s.substring(0, i) + (new StringBuilder(s.substring(i, j + 1))).reverse() + ((j + 1 <= s.length() - 1) ? s.substring(j + 1) : "");}
    Reader sc = new Reader(); public static void main(String[] args) throws Exception{new Main();}
    static class Reader{
        final private int BUFFER_SIZE = 1 << 22;
        private DataInputStream din;private byte[] buffer;
        private int bufferPointer, bytesRead;public Reader(){
            din = new DataInputStream(System.in);
            buffer = new byte[BUFFER_SIZE];bufferPointer = bytesRead = 0;}
            public Reader(String file_name) throws IOException
            {din = new DataInputStream(new FileInputStream(file_name));
            buffer = new byte[BUFFER_SIZE];bufferPointer = bytesRead = 0;}
            public String readLine() throws IOException{byte[] buf = new byte[1<<18];
            int cnt = 0, c;while ((c = read()) != -1)
            {if (c == '\n')break;buf[cnt++] = (byte) c;}
            return new String(buf, 0, cnt);}
            public int nextInt() throws IOException{    int ret = 0;    byte c = read();    while (c <= ' ')        c = read();    boolean neg = (c == '-');    if (neg)        c = read();    do    {        ret = ret * 10 + c - '0';    }  while ((c = read()) >= '0' && c <= '9');    if (neg)        return -ret;    return ret;}public long nextLong() throws IOException{    long ret = 0;    byte c = read();    while (c <= ' ')        c = read();    boolean neg = (c == '-');    if (neg)        c = read();    do {        ret = ret * 10 + c - '0';    }    while ((c = read()) >= '0' && c <= '9');    if (neg)        return -ret;    return ret;}public double nextDouble() throws IOException{    double ret = 0, div = 1;    byte c = read();    while (c <= ' ')        c = read();    boolean neg = (c == '-');    if (neg)        c = read();    do {        ret = ret * 10 + c - '0';    }    while ((c = read()) >= '0' && c <= '9');    if (c == '.')    {        while ((c = read()) >= '0' && c <= '9')        {            ret += (c - '0') / (div *= 10);        }    }    if (neg)        return -ret;    return ret;}private void fillBuffer() throws IOException{    bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);    if (bytesRead == -1)        buffer[0] = -1;}private byte read() throws IOException{    if (bufferPointer == bytesRead)        fillBuffer();    return buffer[bufferPointer++];}public void close() throws IOException{    if (din == null)        return;    din.close();}} Main() throws Exception{if (multiple){ int q = sc.nextInt();for (int i = 0; i < q; i++) solve();} else solve(); out.close();} PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
}