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.BufferedWriter;
import java.io.DataInputStream;
import java.io.IOException;
import java.io.OutputStreamWriter;
import java.util.Arrays;

public class Task {
  private static final int IO_BUFFERS = 1024;
  private static FastReader reader = new FastReader();
  private static FastWriter out = new FastWriter();

  public static void main(String[] args) {
    long startTime = System.currentTimeMillis();
    try {
      for (int i = 0; i < 1; i++) new Solution();
    } catch (IOException e) {
      throw new RuntimeException(e);
    }
    System.err.println("\ntime: " + (System.currentTimeMillis() - startTime) + "ms");
  }

  static class Solution {
    private final double MAX_VALUE = 1e17;
    int Q;
    long[] c = new long[64];
    long[] h = new long[64];

    public Solution() throws IOException {
      readInput();
      solve();
      out.flush();
    }

    private void readInput() throws IOException {
      Q = reader.nextInt();
    }

    private String innerSolve() throws IOException {
      int N = reader.nextInt();
      int K = reader.nextInt();

      long v = 1;
      int p = -1;
      while (v < MAX_VALUE) {
        c[++p] = v;
        v *= K;
      }
      Arrays.fill(h, 1);

      Long[] a = new Long[N];
      for (int i = 0; i < N; i++) a[i] = reader.nextLong();

      for (int i = 0; i < N; i++) {
        long n = a[i];

        for (int j = p; j >= 0; j--) {
//          System.out.println(n + " -- " + j + " " + c[j] + " " + h[j] + " :: " + n / c[j] + " " + h[j]);
          if (n < c[j]) continue;

          if (n / c[j] > h[j]) {
            return "NO";
          } else {
            h[j]--;
            n = n % c[j];
          }
        }
      }

      return "YES";
    }

    private void solve() throws IOException {
      for (int q = 0; q < Q; q++) {
        out.println(innerSolve());
      }
    }
  }

  static class FastWriter {
    public final BufferedWriter out;

    public FastWriter() {
      out = new BufferedWriter(new OutputStreamWriter(System.out), IO_BUFFERS);
    }

    public void print(String str) throws IOException {
      out.write(str);
    }

    public void printS(String str) throws IOException {
      out.write(str);
      out.write(' ');
    }

    public void println(String str) throws IOException {
      out.write(str);
      out.write('\n');
    }

    void flush() throws IOException {
      out.flush();
    }
  }

  static class FastReader {
    private DataInputStream din;
    private byte[] buffer;
    private int bufferPointer;
    private int bytesRead;

    public FastReader() {
      din = new DataInputStream(System.in);
      buffer = new byte[IO_BUFFERS];
      bufferPointer = bytesRead = 0;
    }

    public int nextInt() throws IOException {
      int ret = 0;
      byte c = read();
      while (c <= ' ') c = read();
      do {
        ret = ret * 10 + c - '0';
      } while ((c = read()) >= '0' && c <= '9');
      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;
    }

    private void fillBuffer() throws IOException {
      bytesRead = din.read(buffer, bufferPointer = 0, IO_BUFFERS);
      if (bytesRead == -1) buffer[0] = -1;
    }

    public String readLine() throws IOException {
      StringBuilder sb = new StringBuilder();
      int c;
      while ((c = read()) != -1) {
        if (c == '\n') {
          if (sb.length() > 0) break;
          else continue;
        }
        sb.append((char) c);
      }
      return sb.toString();
    }

    private byte read() throws IOException {
      if (bufferPointer == bytesRead) fillBuffer();
      return buffer[bufferPointer++];
    }

    public void close() throws IOException {
      if (din == null) return;
      din.close();
    }
  }
}
