t, b = map(int, input().split())

def solve(n):
    if n == 0:
        print(0)
        return

    A = []
    x = 1
    y = abs(b)
    while n != 0:
        c = 0
        while n % y != 0:
            c += 1
            n -= x
        A.append(c)
        x *= b
        y *= abs(b)
    print(*A[::-1], sep="")

for _ in range(t):
    n = int(input())
    solve(n)