Suppose you are performing the following algorithm. There is an array $v_1, v_2, \dots, 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 \le pos \le 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 \le T \le 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 \le n \le 30$, $2 \le k \le 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, \dots, a_n$ ($0 \le a_i \le 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$.

Difficulty: interview

Starter code:

Solutions:
t = int(input())
for _ in range(t):
    n,k = list(map(int,input().split()))
    a = list(map(int,input().split()))
    for i in range(60, -1, -1):
        m = k ** i
        for j in range(n):
            if a[j] >= m:
                a[j] -= m
                break
    if all(i == 0 for i in a):
        print('YES')
    else:
        print('NO')


from sys import stdin,stdout                           #
import math                                            #
import heapq                                           #
                                                       #
t = 1                                                  #
def aint():                                            #
	return int(input().strip())                        #
def lint():                                            #
	return list(map(int,input().split()))              #
def fint():                                            #
	return list(map(int,stdin.readline().split()))     #
                                                       #	
########################################################

def main():
	n,k=map(int,input().split())
	cnt=[0]*100
	for i in lint():
		for j in range(60):
			cnt[j]+=i%k
			i//=k
	for i in cnt:
		if i>1:
			print("NO")
			break
	else:
		print("YES")

t=int(input())

########################################################
for i in range(t):                                     #
	main()                                             #

from sys import stdin
for testcase in range(int(stdin.readline())):
    n, k = list(map(int, stdin.readline().split()))
    has_ans = True
    picked = set()
    for num in map(int, stdin.readline().split()):
        i = 0
        while (num > 0) and has_ans:
            while num % k == 0:
                num //= k
                i += 1
            if i in picked:
                has_ans = False
                break
            picked.add(i)
            num -= 1
        if not has_ans:
            break
    print('YES' if has_ans else 'NO')



import sys
input=lambda: sys.stdin.readline().rstrip()
t=int(input())
for _ in range(t):
  n,k=list(map(int,input().split()))
  A=[int(i) for i in input().split()]
  B=[0]*100
  for a in A:
    ct=0
    while a:
      B[ct]+=a%k
      a//=k
      ct+=1
  print("YES" if max(B)<=1 else "NO")


from math import inf
t = int(input())
for q in range(t):
    n, k = [int(i) for i in input().split()]
    L = [int(i) for i in input().split()]
    F = [0] * 60
    for i in L:
        num = i
        step = 0
        while num:
            F[step] += num % k
            num //= k
            step += 1
    flag = True
    for i in F:
        if i > 1:
            flag = False
            break
    if flag:
        print("YES")
    else:
        print("NO")
    


t = int(input())
for case_num in range(t):
    n, k = list(map(int, input().split(' ')))
    a = list(map(int, input().split(' ')))
    d = dict()
    for i in a:
        num = i
        level = 0
        while num > 0:
            if not level in d:
                d[level] = 0
            d[level] += num % k
            num //= k
            level += 1
    ok = True
    for i in d:
        if d[i] > 1:
            ok = False
            break
    print("YES" if ok else "NO")