#include<iostream>
using namespace std;

void zhuan(int n,int b){
	if (n>0){
		zhuan(n/b,b);
		if (n%b<10) cout<<n%b;
		else cout<<char(n%b+'A'-10);
	}
}

int main(){
	int t,n,b;
	cin>>t;
	for (int i=1; i<=t; i++){
		cin>>n>>b;
		if (b==16) cout<<"0X";
		if (n==0){
			cout<<0<<endl;
			continue;
		}
		zhuan(n,b);
		cout<<endl;
	}
	return 0;
}
/**************************************************************
	Problem: 2065
	User: admin
	Language: C++
	Result: Accepted
	Time:17 ms
	Memory:2072 kb
****************************************************************/