m = input().split()
t = int(m[0])
b1 = int(m[1])
num5 = []
for num4 in range(t):
    n = int(input())
    num5.append(n)
for i in range(t):
    num6 = num5[i]
    j = 0
    num3 = []

    while True:
        if j % 2 == 0:
            if abs(num6) >= abs(b1):
                num3.append(abs(num6) % abs(b1))
                num6 = abs(num6) // abs(b1)
            else:
                break
            j += 1
        else:
            if num6 >= b1:
                num3.append(abs(num6) % b1)
                num6 = abs(num6) // b1
            else:
                break
            j += 1

    num3.append(num6)
    num2 = j
    str1 = ''
    while num2 >= 0:
        str1 += str(abs(num3[num2]))
        num2 -= 1
    print(str1)