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


def solve(N):
    lst = []
    while N:
        N, m = divmod(N, B)
        if m < 0:
            m -= B
            N += 1
        lst.append(m)
    res = ''.join(map(str, reversed(lst)))
    if not res:
        res = 0
    return res


for _ in range(T):
    print(solve(int(input())))