#include<bits/stdc++.h>
using namespace std;
string code[16]=
{
	"0000",
	"0001",
	"0010",
	"0011",
	"0100",
	"0101",
	"0110",
	"0111",
	"1000",
	"1001",
	"1010",
	"1011",
	"1100",
	"1101",
	"1110",
	"1111",
};
int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		string s,s1="",s2="",s3="";
		int m,i,j;
		long long k;
		cin>>s;
		scanf("%d%lld",&m,&k);
		//cout<<k<<endl;
		int len=s.size();
		for(i=0;i<len;i++)
		{
			if(s[i]>='0'&&s[i]<='9')
			{
				s1+=code[s[i]-'0'];
			}
			else if(s[i]=='a') s1+=code[10];
			else if(s[i]=='b') s1+=code[11];
			else if(s[i]=='c') s1+=code[12];
			else if(s[i]=='d') s1+=code[13];
			else if(s[i]=='e') s1+=code[14];
			else if(s[i]=='f') s1+=code[15];
		}
		int len1=s1.size();
		while(k)
		{
			s2+=(k%2)+'0';
			k/=2;
		}
		int len2=s2.size();
		for(i=len2;i<m;i++) s2+="0";
		/*else
		{
			s2.erase(m,len2-m);
		}*/
		len2=s2.size();
		/*for(i=len2-1,j=0;j<m;i--,j++) cout<<s2[i];
		cout<<endl;*/
		//cout<<endl;
		//cout<<s1<<endl;
		for(i=0,j=len2-1;i<m;i++,j--)
		{
			s1[i]=s2[j];
		}
		//cout<<s1<<endl;
		for(i=0;i<len1;i+=4)
		{
			s3+=s1[i],s3+=s1[i+1],s3+=s1[i+2],s3+=s1[i+3];
			//cout<<s3<<endl;
			for(j=0;j<16;j++)
			{
				if(s3==code[j])
				{
					if(j<=9&&j>=0) printf("%d",j);
					else if(j==10) printf("a");
					else if(j==11) printf("b");
					else if(j==12) printf("c");
					else if(j==13) printf("d");
					else if(j==14) printf("e");
					else if(j==15) printf("f");
				}
			}
			s3="";
		}
		cout<<endl;
	}
}