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

int main()
{
	int t,i;
	scanf("%d",&t);
	getchar();
	while(t--)
	{
		char a[20];
		int tdz[64];
		scanf("%s",a);
		for(i=0;i<8;i++)
		{
			int c;
			if(a[i]>='0'&&a[i]<='9')
				c=a[i]-'0';
			else if(a[i]=='a')
				c=10;
			else if(a[i]=='b')
				c=11;
			else if(a[i]=='c')
				c=12;
			else if(a[i]=='d')
				c=13;
			else if(a[i]=='e')
				c=14;
			else if(a[i]=='f')
				c=15;
			tdz[(i+1)*4-1]=c%2;
			c/=2;
			tdz[(i+1)*4-2]=c%2;
			c/=2;
			tdz[(i+1)*4-3]=c%2;
			c/=2;
			tdz[(i+1)*4-4]=c;
		}
		int k,m;
		scanf("%d%d",&k,&m);
		int wdz[64]={0};
		int t=1;
		while(m>=2&&k-t>=0)
		{
			wdz[k-t]=m%2;
			t++;
			m/=2;
		}
		if(k-t>=0)
			wdz[k-t]=m%2;
		for(i=0;i<k;i++)
		{
			tdz[i]=wdz[i];
		}
		int total=0;
		char pr[20];
		for(i=0;i<8;i++)
		{
			total=tdz[(i+1)*4-4]*8+tdz[(i+1)*4-3]*4+tdz[(i+1)*4-2]*2+tdz[(i+1)*4-1];
			if(total==10)
				pr[i]='a';
			else if(total==11)
				pr[i]='b';
			else if(total==12)
				pr[i]='c';
			else if(total==13)
				pr[i]='d';
			else if(total==14)
				pr[i]='e';
			else if(total==15)
				pr[i]='f';
			else
				pr[i]=total+48;
			total=0;
		}
		for(i=0;i<8;i++)
		{
			printf("%c",pr[i]);
		}printf("\n");
	}
	return 0;
}