#include<stdio.h>
#include<string.h>
struct strings{
	char str[5];
};
int main(void){
	struct strings strs[8];
    char a[9],b[33],c[33];
	int i=0,n,m,t;
	scanf("%d",&t); 
	while(t--){
	    scanf("%s",a);
	    for(i=0;i<8;i++){
		    switch(a[i]){
			    case '0':strcpy(strs[i].str,"0000");break;
			    case '1':strcpy(strs[i].str,"0001");break;
			    case '2':strcpy(strs[i].str,"0010");break;  
			    case '3':strcpy(strs[i].str,"0011");break;
				case '4':strcpy(strs[i].str,"0100");break;
				case '5':strcpy(strs[i].str,"0101");break;
				case '6':strcpy(strs[i].str,"0110");break;
				case '7':strcpy(strs[i].str,"0111");break;
				case '8':strcpy(strs[i].str,"1000");break;
				case '9':strcpy(strs[i].str,"1001");break;
				case 'a':strcpy(strs[i].str,"1010");break;
				case 'b':strcpy(strs[i].str,"1011");break;
				case 'c':strcpy(strs[i].str,"1100");break;
				case 'd':strcpy(strs[i].str,"1101");break;
				case 'e':strcpy(strs[i].str,"1110");break;
				case 'f':strcpy(strs[i].str,"1111");break;		 		 		 		 		 		 		 		 		 		 		 		       
			}
			if(i==0){
				strcpy(b,strs[i].str); 
			}
			if(i>0){
				strcat(b,strs[i].str);
			}
		}
    scanf("%d%d", &n,&m) ;
	int x=0; 
    do {
        c[x++]=m%2+'0';
        m/=2;
    } while(m!=0);
    int r;
    for(r=0;r<n-x;r++){  
    	b[r]='0';
	}
	int p=x-1;
	int q;
	for(q=n-x;q<n;q++){    
    	b[q]=c[p];
    	p--;
	}
	char d[5]={""};
	int h;
	for(h=0;h<8;h++){
		strncpy(d,b+4*h, 4);  
         if(strcmp(d,"0000")==0){
         	printf("0");
		 }
		 if(strcmp(d,"0001")==0){
         	printf("1");
		 }
		 if(strcmp(d,"0010")==0){
         	printf("2");
		 }
		 if(strcmp(d,"0011")==0){
         	printf("3");
		 }
		 if(strcmp(d,"0100")==0){
         	printf("4");
		 }
		 if(strcmp(d,"0101")==0){
         	printf("5");
		 }
		 if(strcmp(d,"0110")==0){
         	printf("6");
		 }
		 if(strcmp(d,"0111")==0){
         	printf("7");
		 }
		 if(strcmp(d,"1000")==0){
         	printf("8");
		 }
		 if(strcmp(d,"1001")==0){
         	printf("9");
		 }
		 if(strcmp(d,"1010")==0){
         	printf("a");
		 }
		 if(strcmp(d,"1011")==0){
         	printf("b");
		 }
		 if(strcmp(d,"1100")==0){
         	printf("c");
		 }
		 if(strcmp(d,"1101")==0){
         	printf("d");
		 }
		 if(strcmp(d,"1110")==0){
         	printf("e");
		 }
		 if(strcmp(d,"1111")==0){
         	printf("f");
		 }
	} 
	printf("\n");
}
}