#include<stdio.h>
int  main() {

	int T,m,k,array1[32]= {0};
	char array0[8];

	scanf("%d",&T);

	while(T--) {
		scanf("%s",&array0);
		int array1[8][4]= {0};
		int temp[8]= {0};
		for(int i=0; i<8; ++i) {
			if(array0[i]>='a'&&array0[i]<='f')
				temp[i]=array0[i]-87;
			else
				temp[i]=array0[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[32];
		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");

	}

}