#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<string>
#include<map>
#include<vector>
using namespace std;

int main()
{
	int t,m,k,b[100],c[100];
	char a[100],re[100],hash[16]={'0','1','2','3','4','5','6','7','8','9','a','b','c','d','e','f'};
	scanf("%d",&t);
	while(t--)
	{	
		getchar();
		gets(a);
		scanf("%d%d",&m,&k);
		int l=0,temp;
		for(int i=0;i<8;i++)
		{
			for(int j=0;j<=15;j++)
			{
				if(hash[j]==a[i])
				{
					temp=j;
				}
			}
			b[l+3]=temp%2;temp/=2;
			b[l+2]=temp%2;temp/=2;
			b[l+1]=temp%2;temp/=2;
			b[l]=temp;
			l+=4;
		}
		int count=0;
		while(k)
		{
			c[count++]=k%2;
			k/=2;
		}
		while(count<m)
		{
			c[count++]=0;
		}
		int num=0;
		for(int i=m-1;i>=0;i--)
		{
			b[num++]=c[i];
		}
		int co=0,coo=0;
		for(int i=0;i<32;i+=4)
		{
			co=b[i]*8+b[i+1]*4+b[i+2]*2+b[i+3];
			if(co<=9)
			{
				re[coo++]=co+'0';
			}
			else
			{
				if(co==10)
					re[coo++]='a';
				if(co==11)
					re[coo++]='b';
				if(co==12)
					re[coo++]='c';
				if(co==13)
					re[coo++]='d';
				if(co==14)
					re[coo++]='e';
				if(co==15)
					re[coo++]='f';
			}
		}
		for(int i=0;i<=7;i++)
		{
			printf("%c",re[i]);
		}
		printf("\n");
	}

	return 0;
}