#!/usr/bin/python2
# -*- coding: utf-8 -*-
# †
import string

def int2negbase(num, base, digits=string.digits+string.ascii_uppercase):
    assert base < -1
    num = -num
    if num == 0:
        return digits[0]
    s = ''
    while num != 0:
        s = digits[-(num % base)] + s
        num /= base
    return s

T, B = map(int, raw_input().split())
for loop in xrange(T):
    N = int(raw_input())
    res = int2negbase(N, B)
    print res