#include <stdio.h>
#include <stdlib.h>

#define bianWord(x) (x+55)
#define bianNum(x) (x+'0')
/* run this program using the console pauser or add your own getch, system("pause") or input loop */

int main(int argc, char *argv[]) {
	int n;
	while(scanf("%d",&n)!=EOF){
		
		while(n--){
			long long a;
		int b;
		char c[100];
		scanf("%lld%d",&a,&b);
		int size=0;
		if(a==0) {
		printf("0\n");
		continue;	
		}
		while(a>0){
			int temp=a%b;
			if(temp<10)
			c[size++]=bianNum(temp);
			else 
			c[size++]=bianWord(temp);
			
			a/=b;
		}
		int i;
		if(b==16) printf("0X");
		for(i=size-1;i>=0;i--){
			printf("%c",c[i]);
		}
		printf("\n");
		}
		
	} 
	return 0;
}
/**************************************************************
	Problem: 2065
	User: admin
	Language: C
	Result: Accepted
	Time:16 ms
	Memory:1144 kb
****************************************************************/