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.
# from collections import defaultdict
# from math import ceil,sqrt,log,floor,pi
# def my_log(n,b):
#     p = log(n,b)
#     y,x = ceil(p),floor(p)
#     if(b**x - n <= 0):
#         if(b**y - n==0):
#             return y
#         return x
#     else:
#         return y


# def collectBits(N,Base):
#     Bits = []
#     while(N!=0):
#         Ans = my_log(N,Base)
#         N -= Base ** Ans
#         Bits.append(Base ** Ans)
#     if(len(set(Bits))==len(Bits)):
#         return Bits
#     return -1
# for _ in range(int(input())):
#     N,K = map(int,input().split())
#     List = [int(x) for x in input().split()]
#     Visited = defaultdict(bool)
#     flag = 0
#     for i in range(N):
#         if(List[i]!=0):
#             X = collectBits(List[i],K)
#             if(X==-1):
#                 flag = 1
#                 print("NO")
#                 break
#             else:
#                 for k in X:
#                     if(Visited[k]):
#                         flag = 1
#                         print("NO")
#                         break
#                     else:
#                         Visited[k] = True
#                 if(flag):
#                     break
#     if(not flag):
#         print("YES")
from math import ceil,sqrt,log,floor,pi
for _ in range(int(input())):
    N,K = map(int,input().split())
    List = [int(x) for x in input().split()]
    StartPower = int(ceil(log(10**16,K)))
    Visited = [False] * (StartPower + 1)
    flag = 0
    for i in range(N):
        CopyPower = StartPower
        val = List[i]
        while(val!=0):
            if(val>=(K**CopyPower)):
                val-=(K**CopyPower)
                if(Visited[CopyPower]):
                    flag = 1
                    print("NO")
                    break
                else:
                    Visited[CopyPower] = True
            CopyPower-=1
        if(flag):
            break
    if(not flag): print("YES")