#include<stdio.h>
int main() {
	long n,m,t,i,j,k,p;
	long f[100];
	char ch;
	scanf("%ld%c",&t,&ch);
	while (t--) {
		for (i=1;i<=8;++i) {
			scanf("%c",&ch);
			if (ch>='0'&&ch<='9') p=ch-48;
			else p=ch-87;
			for (j=i*4;j>=i*4-3;--j) {f[j]=p%2;p=p/2;}
		}
		scanf("%ld",&n);scanf("%ld%c",&m,&ch);
		for (i=n;i>=1;--i) {f[i]=m%2;m=m/2;}
		for (i=1;i<=8;++i) {
			p=f[i*4]+f[i*4-1]*2+f[i*4-2]*4+f[i*4-3]*8;
			if (p<10) printf("%ld",p);
			else printf("%c",p+87);
		}	
		printf("\n");
	}
}