import sys

def convert_to_negative_base(n, b):
    if n == 0:
        return '0'
    digits = []
    m = abs(b)
    while n != 0:
        r = n % m
        digits.append(r)
        n = (n - r) // b
    # Reverse to get the correct order
    return ''.join(map(str, reversed(digits)))

def main():
    input = sys.stdin.read().split()
    idx = 0
    T = int(input[idx])
    idx +=1
    B = int(input[idx])
    idx +=1
    for _ in range(T):
        N = int(input[idx])
        idx +=1
        print(convert_to_negative_base(N, B))

if __name__ == '__main__':
    main()