#include<stdio.h>
int main(void){
	int T;                    
	char alist[8];            
	int m,k;                             
	scanf("%d",&T); 
	while(T--){
		scanf("%s",&alist);
		//array1为存储原二进制 
		int array1[8][4]={0};
		//temp是将输入的八位字符串数组变为数字数组           
		int temp[8]={0};
		for(int i=0;i<8;i++){                            
			if(alist[i]>='a'&&alist[i]<='f')temp[i]=alist[i]-87;
			else temp[i]=alist[i]-48;
		}
		//十六进制代码变为二进制 
		for(int i=0;i<8;i++){
			if(temp[i]%2!=0)array1[i][3]=1;
			if(temp[i]/2%2!=0)array1[i][2]=1;
			if(temp[i]/4%2!=0)array1[i][1]=1;
			if(temp[i]/8%2!=0)array1[i][0]=1;
		}
		//存储修改后的二进制代码 
		int array3[32]={0};
		//将原二进制放入存储存储修改后数据的数组中 
		for(int i=0;i<4;i++)array3[i]=array1[0][i];
		for(int i=4;i<8;i++)array3[i]=array1[1][i-4];
		for(int i=8;i<12;i++)array3[i]=array1[2][i-8];
		for(int i=12;i<16;i++)array3[i]=array1[3][i-12];
		for(int i=16;i<20;i++)array3[i]=array1[4][i-16];
		for(int i=20;i<24;i++)array3[i]=array1[5][i-20];
		for(int i=24;i<28;i++)array3[i]=array1[6][i-24];
		for(int i=28;i<32;i++)array3[i]=array1[7][i-28];
		scanf("%d%d",&m,&k);
		getchar();
		int array2[m];
		for(int i=0;i<m;i++){
			array2[i]=0;
		}
		//替换部分 
		for(int i=0;i<m,k!=0;i++,k/=2){
			if(k%2!=0)array2[m-1-i]=1;
		}
		//将替换部分放入 
		for(int i=0;i<m;i++){
			array3[i]=array2[i];
		}
		//将二进制转换为十六进制 
		int array4[8]={0};
		for(int i=0,j=0;i<32,j<8;i+=4,j++){
			array4[j]=array3[i]*8+array3[i+1]*4+array3[i+2]*2+array3[i+3];
		}
		for(int i=0;i<8;i++){
			if(array4[i]==10)printf("a");
			if(array4[i]==11)printf("b");
			if(array4[i]==12)printf("c");
			if(array4[i]==13)printf("d");
			if(array4[i]==14)printf("e");
			if(array4[i]==15)printf("f");
			if(array4[i]<10)printf("%d",array4[i]);
		}
		printf("\n");
	}
}