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

def solve():
    N = int(raw_input())
    ans = []
    while N != 0:
        m = N % B
        if m < 0:
            m -= B
        ans.append(m)
        N /= -B
        N *= -1
    print "".join(map(str, reversed(ans)))

for _ in xrange(T):
    solve()