#include<bits/stdc++.h>

using namespace std;

int main() {
	int t;
	scanf("%d",&t);
	getchar();
	while (t--) {
		char s[8];
		int m,k;
		scanf("%s",s);
		scanf("%d%d",&m,&k);
		int a[32];
		int z[4];
		int x;
		for (int i=0; i<32;) {
			for (int j=0; j<8; ++j) {
				if (s[j]>=48&&s[j]<=58) {
					x=s[j]-48;
				} else if (s[j]>=97&&s[j]<=102) {
					x=s[j]-97+10;
				}
				int w=0;
				while (x) {
					z[w++]=x%2;
					x/=2;
				}
				for (int l=w;l<4;++l){
					a[i++]=0;
				}
				for (int l=w-1;l>=0;--l){
					a[i++]=z[l];
				}
			}
		}
		int b[m],l=m-1;
		memset(b,0,sizeof(b));
		while (k){
			b[l--]=k%2;
			k/=2;
		}
		for (int i=0;i<m;++i){
			a[i]=b[i];
		}
		int sum=0;
		for (int i=0;i<32;i+=4){
			sum=8*a[i]+4*a[i+1]+2*a[i+2]+1*a[i+3];
			if (sum<10){
				printf("%d",sum);
			}else{
				printf("%c",sum+87);
			}
		}
		printf("\n");
	}
	return 0;
}