#include<stdio.h>
#include<stdlib.h>
int s[32];
char str[9];
int main(void){
	int t,i,j;
	scanf("%d",&t);
	for(i=0;i<t;i++){
		int m,k,a;
		getchar();
		gets(str);
		scanf("%d",&m);
		scanf("%d",&k);
	    for(j=0;j<8;j++){
	    	if(str[j]<='9'&&str[j]>='0')
	    	a=str[j]-'0';
	    	else
	    	a=str[j]-'0'-39;
	    	s[4*j+3]=a%2;
	    	s[4*j+2]=a/2%2;
	    	s[4*j+1]=a/2/2%2;
	    	s[4*j]=a/2/2/2%2;
		}
	    for(j=1;j<=m;j++){
	    	s[m-j]=k%2;
	    	k/=2;
		}
		for(j=0;j<8;j++){
			a=s[4*j+3]+2*s[4*j+2]+4*s[4*j+1]+8*s[4*j];
			if(a>=10)
			str[j]='0'+a+39;
			else
			str[j]='0'+a;
		}
		for(j=0;j<8;j++){
			printf("%c",str[j]);
		}
		printf("\n");
	}
	return 0;
}