T,B=map(int,input().split()) for i in range(T): ANS="" N=int(input()) if N==0: print(0) continue for i in range(1,100): if N==0: break x=N%(-B**i) ANS+=str(x//(B**(i-1))) N-=x #print(N,ANS) print(ANS[::-1])