def trans(X, K):
    #K進数で変換
    if 0 < X < -K:
        return str(X)
    if X == 0:
        return "0"
    U, V = divmod(X, K)
    if V < 0:
        U += 1
        return trans(U, K)+str(V-K)
    else:
        return trans(U, K)+str(V)


T, B = map(int, input().split())
for _ in range(T):
    N = int(input())
    print(trans(N, B))