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 math import log2
# t = int(input())

# while t:
#     n = int(input())
#     mem = {}
#     def f(num):
#         if num in mem:
#             n = mem[num]
#         #print(num)
#         #n = int(log2(num))
#         else:
#             n = 0
#             x = num
#             while x:
#                 if x in mem:
#                     n+=mem[x]
#                     break
#                 x=x//2
#                 #print(1)
#                 n+=1
#                 #mem[x] = n-1
#             n-=1
#         mem[num] = n
    #     # print(num,n,2**n,num-(2**n))
    #     return num-(2**n),2**(n+1)-1
    # ans = 0

    # remain = n
    # while remain>0:
    #     remain,v = f(remain)
    #     #print(remain)
    #     ans+=v
        
    # print(ans)
    
    # t-=1
    
# from math import sqrt
# def divs(n) :
#     ans = []
#     i = 1
#     while i <= sqrt(n): 
#         if (n % i == 0) : 
#             if (n / i == i) : 
#                 ans.append((i,i)) 
#             else : 
#                 ans.append((i,n/i))
#         i = i + 1
#     return ans
        
# n,m,k = [int(i) for i in input().split()]

# a = [int(i) for i in input().split()]
# c= [int(i) for i in input().split()]

# l = {}
# b = {}
# prevl = -1
# for i in range(n+1):
#     if i==n or a[i] == 0:
#         leng = i-prevl-1
#         if leng != 0:
#             if leng in l:
#                 l[leng]+=1
#             else:
#                 l[leng] = 1
#         prevl = i
        
# prevb = -1
# for i in range(m+1):
#     if i == m or c[i] == 0:
#         br = i-prevb-1
#         if br != 0:
#             if br in b:
#                 b[br]+=1
#             else:
#                 b[br] = 1
#         prevb = i

# d = divs(k)
# ans = 0
# for le in l.keys():
#     for br in b.keys():
#         for a,b1 in d:
#             a = int(a)
#             b1 = int(b1)
#             if le>=a and br>=b1:
#                 ans+=((le-a+1)*(br-b1+1)*l[le]*b[br])
#                 if a==b1:
#                     continue
#             if le>=b1 and br>=a:
#                 ans+=((le-b1+1)*(br-a+1)*l[le]*b[br])
                
        
# print(ans) 


t = int(input())

while t:
    
    n,k = [int(i) for i in input().split()]
    a = [int(i) for i in input().split()]
    a.sort()
    
    def f(num):
        ans = []
        i=0
        #print(num)
        while num>0:
            if num%k == 1:
                ans.append(i)
            elif num%k >1:
                return ans,False
            i+=1
            num = num//k
        return ans,True
        
    bits = []
    flag = 0
    for e in a:
        x,z = f(e)
        if z:
            bits.append(x)
        else:
            flag = 1
            break
    # print(a)
    # print(bits)    
    if flag == 1:
        print('NO')
        t-=1
        continue
    flag = 0
    mem = set()
    for i in range(n):
        if a[i] == 0:
            continue
        for l in bits[i]:
            if l in mem:
                flag = 1
                break
            mem.add(l)
    if flag == 1:
        print('NO')
    else:
        print('YES')
    t-=1