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.util.*;

import javax.sound.sampled.ReverbType;

import java.io.*;

public class B {
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		PrintWriter pw = new PrintWriter(System.out);

		int t = Integer.parseInt(br.readLine());

		while (t-- > 0) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int n = Integer.parseInt(st.nextToken());
			int k = Integer.parseInt(st.nextToken());
			ArrayList<Long> arr = new ArrayList<>();
			long ans = 1;
			for (int i = 0; i < 70 && ans < 1e17; i++) {
				arr.add(ans);
				ans = pow(k, i + 1);
			}
			long[] a = new long[n];
			st = new StringTokenizer(br.readLine());
			for (int i = 0; i < a.length; i++) {
				a[i] = Long.parseLong(st.nextToken());
			}
			vis = new boolean[arr.size()];
			boolean f = true;
			for (int i = 0; i < a.length; i++) {
				if (!check(a[i], arr))
					f = false;

			}
			if (f)
				pw.println("YES");
			else
				pw.println("NO");
		}
		pw.println();
		pw.flush();

	}

	static boolean[] vis;

	static boolean check(long x, ArrayList<Long> arr) {
		for (int i = vis.length - 1; i >= 0 && x != 0; i--) {
			if (!vis[i] && arr.get(i) <= x) {
				x -= arr.get(i);
				vis[i] = true;
			}
		}
//		System.out.println(x);
		return x == 0;
	}

	static long pow(long a, long e) // O(log e)
	{
		long res = 1;
		while (e > 0) {
			if ((e & 1) == 1)
				res *= a;
			a *= a;
			e >>= 1;
		}
		return res;
	}

	static String rev(String s) {
		StringBuilder sb = new StringBuilder();
		for (int i = s.length() - 1; i >= 0; i--) {
			sb.append(s.charAt(i));
		}
		return sb.toString();
	}

	static class triple implements Comparable<triple> {
		int x;
		int y;
		int z;

		public triple(int a, int b, int c) {
			x = a;
			y = b;
			z = c;
		}

		@Override
		public int compareTo(triple o) {
			// TODO Auto-generated method stub
			return x - o.x;
		}
	}

	static long gcd(long a, long b) {
		if (a == 0)
			return b;
		return gcd(b % a, a);
	}

	static long lcm(long a, long b) {
		return a / gcd(a, b) * b;
	}

	static class SegmentTree { // 1-based DS, OOP

		int N; // the number of elements in the array as a power of 2 (i.e. after padding)
		long[] array, sTree, lazy;

		SegmentTree(long[] in) {
			array = in;
			N = in.length - 1;
			sTree = new long[N << 1];
			Arrays.fill(sTree, 1);// no. of nodes = 2*N - 1, we add one to cross out index zero
			lazy = new long[N << 1];
			build(1, 1, N);
		}

		void build(int node, int b, int e) // O(n)
		{
			if (b == e)
				sTree[node] = array[b];
			else {
				int mid = b + e >> 1;
				build(node << 1, b, mid);
				build(node << 1 | 1, mid + 1, e);
				sTree[node] = lcm(sTree[node << 1], sTree[node << 1 | 1]);
			}
		}

		void update_point(int index, int val) // O(log n)
		{
			index += N - 1;
			sTree[index] += val;
			while (index > 1) {
				index >>= 1;
				sTree[index] = sTree[index << 1] + sTree[index << 1 | 1];
			}
		}

		void update_range(int i, int j, int val) // O(log n)
		{
			update_range(1, 1, N, i, j, val);
		}

		void update_range(int node, int b, int e, int i, int j, int val) {
			if (i > e || j < b)
				return;
			if (b >= i && e <= j) {
				sTree[node] += (e - b + 1) * val;
				lazy[node] += val;
			} else {
				int mid = b + e >> 1;
				propagate(node, b, mid, e);
				update_range(node << 1, b, mid, i, j, val);
				update_range(node << 1 | 1, mid + 1, e, i, j, val);
				sTree[node] = sTree[node << 1] + sTree[node << 1 | 1];
			}

		}

		void propagate(int node, int b, int mid, int e) {
			lazy[node << 1] += lazy[node];
			lazy[node << 1 | 1] += lazy[node];
			sTree[node << 1] += (mid - b + 1) * lazy[node];
			sTree[node << 1 | 1] += (e - mid) * lazy[node];
			lazy[node] = 0;
		}

		long query(int i, int j) {
			return query(1, 1, N, i, j);
		}

		long query(int node, int b, int e, int i, int j) // O(log n)
		{
			if (i > e || j < b)
				return 1;
			if (b >= i && e <= j)
				return sTree[node];
			int mid = b + e >> 1;
			long q1 = query(node << 1, b, mid, i, j);
			long q2 = query(node << 1 | 1, mid + 1, e, i, j);
			return lcm(q1, q2);

		}

	}

	static int[][] z;
	static int[] memo;

	static int dp(int s) {
		if (s == z.length)
			return 0;
		if (memo[s] != -1)
			return memo[s];
		int max = 0;
		for (int i = s; i < z.length; i++) {
			if (z[s][i] == 1) {
				if (i == z.length - 1)
					max = Math.max(max, 1 + dp(i + 1));
				else if (z[i + 1][z.length - 1] == 1)
					max = Math.max(max, 1 + dp(i + 1));
			}
		}
		return memo[s] = max;
	}

	static class pair implements Comparable<pair> {
		int x;
		int y;

		public pair(int d, int u) {
			x = d;
			y = u;
		}

		@Override
		public int compareTo(pair o) {
			// TODO Auto-generated method stub
			return o.x - x;
		}

	}

	static int[] nxtarr(StringTokenizer st) {
		int[] a = new int[st.countTokens()];
		for (int i = 0; i < a.length; i++) {
			a[i] = Integer.parseInt(st.nextToken());
		}
		return a;
	}

}
