#include<iostream>
using namespace std;

int main(){
	int T;                   
	char array0[8];           
	int m,k;                 
	int array1[32]={0};         
	cin>>T;

	while(T--){
		cin>>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];


		cin>>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)
				cout<<"a";
			if(array4[i]==11)
				cout<<"b";
			if(array4[i]==12)
				cout<<"c";
			if(array4[i]==13)
				cout<<"d";
			if(array4[i]==14)
				cout<<"e";
			if(array4[i]==15)
				cout<<"f";
			if(array4[i]<10)
				cout<<array4[i];
		}
		cout<<endl;
	}
}