#include<stdio.h>
int main(void){
	int T;                     
	char a[8];            
	int m,k;                 
	int b[32]={0};       
	scanf("%d",&T); 
	while(T--){
		scanf("%s",&a);
		int b[8][4]={0};          
		int temp[8]={0};
		for(int i=0;i<8;i++){                            
			if(a[i]>='a'&&a[i]<='f'){
			temp[i]=a[i]-87;
		}
			else {
			temp[i]=a[i]-48;
		}
		}
		for(int j=0;j<8;j++){
			if(temp[j]%2!=0){
			b[j][3]=1;
		}
			if(temp[j]/2%2!=0){
			b[j][2]=1;
		}
			if(temp[j]/4%2!=0){
			b[j][1]=1;
		}
			if(temp[j]/8%2!=0){
			b[j][0]=1;
		}
		}
		int c[32]={0};
		for(int j=0;j<4;j++){
		c[j]=b[0][j];
		} 
		for(int j=4;j<8;j++){ 
		c[j]=b[1][j-4];
		} 
		for(int j=8;j<12;j++){ 
		c[j]=b[2][j-8];
		} 
		for(int j=12;j<16;j++){ 
		c[j]=b[3][j-12];
		} 
		for(int j=16;j<20;j++){ 
		c[j]=b[4][j-16];
		} 
		for(int j=20;j<24;j++){ 
		c[j]=b[5][j-20];
		} 
		for(int j=24;j<28;j++){ 
		c[j]=b[6][j-24];
		} 
		for(int j=28;j<32;j++){ 
		c[j]=b[7][j-28];
		} 
		scanf("%d%d",&m,&k);
		getchar();
		int d[m];
		for(int i=0;i<m;i++){
			d[i]=0;
		}
		for(int i=0;i<m,k!=0;i++,k/=2){
			if(k%2!=0)
			d[m-1-i]=1;
		}
		for(int i=0;i<m;i++){
			c[i]=d[i];
		}
		int e[8]={0};
		for(int i=0,j=0;i<32,j<8;i+=4,j++){
			e[j]=c[i]*8+c[i+1]*4+c[i+2]*2+c[i+3];
		}
		for(int i=0;i<8;i++){
			if(e[i]==10)
			printf("a");
			if(e[i]==11)
			printf("b");
			if(e[i]==12)
			printf("c");
			if(e[i]==13)
			printf("d");
			if(e[i]==14)
			printf("e");
			if(e[i]==15)
			printf("f");
			if(e[i]<10)
			printf("%d",e[i]);
		}
		printf("\n");
	}
}