def solve():
    t, b = map(int, input().split())

    o0 = ord('0')

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

        ans = []

        while n:
            n, m = divmod(n, b)
            if m < 0:
                m -= b
                n += 1
            ans.append(m)

        ans = ans[::-1]
        if len(ans) == 0:
            ans = [0]
        print(''.join(chr(o0 + a) for a in ans))


if __name__ == '__main__':
    solve()