T,B = map(int, input().split())

for i in range(T):
    n = int(input())
    ans = []
    t = B
    while n!=0: 
        p = n % t
        if p >= 0:
            ans.append( n % t )
            n //= t
        else:
            ans.append( n % t - t )
            n = (n//t)+1
        
        # t *= B
    ans = list(reversed(ans))
    ans = list(map(str, ans))
    print("".join(ans))