#include<bits/stdc++.h>
using namespace std;
int main(){
    int t,b;
    cin>>t>>b;
    while(t--){
 int N;cin >> N;
 string S = "";
 while(N){
  if(N % b){
	 N--;
	 S = (char)('0'+N%b) + S;
	}
	else{
	 S = '0' + S;
	}
	N /= -b;
 }
 if(S=="")
   cout<<0;
 cout << S << endl;

    }
}