#include<stdio.h>
#include<string.h>

int main(void){
    char a[8];
    int n,m,k;
    scanf("%d",&n);
    while(n--){
    	int sec[8][4]={0},b[8];
    	scanf("%s",a);
    	scanf("%d%d",&m,&k);
    	getchar();
    	for(int i=0;i<8;i++){
    		if(a[i] >= 'a' &&a[i] <= 'f'){
    			b[i] = a[i]-87;
			}
			else{
				b[i] = a[i]-48;
			}		
    		if(b[i] % 2 == 1)
			   sec[i][3] = 1;
    		if(b[i]/2%2 == 1)
			    sec[i][2] = 1;
    		if(b[i]/4%2==1)
			    sec[i][1] = 1;
    		if(b[i] >= 8)
			    sec[i][0] = 1;	
		}
		int secd[m]; 
		for(int i = 0;i <m;i++){
			secd[i] = 0;
		}
		for(int i = 1;i <= m,k!=0;i++){
			secd[m-i] = k%2;
			k/=2;
		}
		for(int i = 0;i < m;i++){
			*(*sec+i) = secd[i]; 
		}	
		for(int i = 0;i < 8;i ++){
			int s = 8*sec[i][0] + 4*sec[i][1] + 2*sec[i][2] + sec[i][3];
			if(s >= 0 &&s <= 9)
			    printf("%d",s);
			else if(s >= 10 && s <= 15)
			    printf("%c",s-10 + 'a');
		}
		printf("\n");
	}
    return 0;
}