def ascan; gets.split.map(&:to_i); end T,B = ascan T.times do n = gets.to_i if n == 0 p 0 next end l = "" i = 0 while n != 0 q, md = n.divmod(-B**(i+1)) n-=md l += (md/(-B**(i))).to_s[-1] i += 1 end puts l.reverse end