t,k=map(int, input().split())
a=[int(input()) for i in range(t)]
for n in a:
    ans=''
    if n==0:ans='0'
    while n!=0:
        if n%-k==0:ans+='0'
        else:ans+=str(n%-k)
        n=-(n//-k)
    print(ans[::-1])