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

int main(void){
    char x[8];
    int n,m,k;
    scanf("%d",&n);
    while(n--){
    	int sec[8][4]={0},xx[8];
    	scanf("%s",x);
    	scanf("%d%d",&m,&k);
    	getchar();
    	//将十六进制的8位字符串转化为2进制的二维数组 
    	for(int i = 0;i<8;i++){
    		if(x[i] >= 'a' &&x[i] <= 'f'){
    			xx[i] = x[i]-87;
			}
			else{
				xx[i] = x[i]-48;
			}		
    		if(xx[i] % 2 == 1)sec[i][3] = 1;
    		if(xx[i]/2%2 == 1)sec[i][2] = 1;
    		if(xx[i]/4%2==1)sec[i][1] = 1;
    		if(xx[i] >= 8)sec[i][0] = 1;	
		}
		
		
		//将mk转为相应的二进制数组
		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;
}