#include<stdio.h>
int main(void){
	int T;                     //T组数据 
	char array[8];            //存放输入的十六进制数 
	int m,k;                  //m：块号位数，k：物理块号值 
	int array1[32]={0};           //将输入的十六进制数转化为二进制 
	scanf("%d",&T); 
	while(T--){
		scanf("%s",&array);
		int array1[8][4]={0};           //将输入的十六进制数转化为二进制 
		int temp[8]={0};
		for(int i=0;i<8;i++){                            //将字符转化为数字 
			if(array[i]>='a'&&array[i]<='f')temp[i]=array[i]-87;
			else temp[i]=array[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");
	}
}