#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int inf = 0x3f3f3f3f;
const int maxn =1e5+10;
int t,m;
ll k;
string s;
int x[1000];
map<char,int>mp;
map<int,char>mp1;
void f(int a,int b)
{
	for(int i=b+3;i>=b;i--)
	{
		x[i]=a%2;
		a/=2;
	}
}
void f2()
{
	for(int i=m;i>=1;i--)
	{
		x[i]=k%2;
		k/=2;
	}
}
int main()
{
	for(int i=0;i<=9;i++)mp['0'+i]=i;
	for(int i=0;i<=5;i++)mp['a'+i]=10+i;
	for(int i=0;i<=9;i++)mp1[i]=i+'0';
	for(int i=0;i<=5;i++)mp1[10+i]='a'+i;
	scanf("%d",&t);
	while(t--)
	{
		cin>>s>>m>>k;
		for(int i=0;i<s.length();i++)
		{
			f(mp[s[i]],4*i+1);
		}
		f2();
		for(int i=1;i<=32;i+=4)
		{
			int num=0;
			num=x[i]*8+x[i+1]*4+x[i+2]*2+x[i+3];
			cout<<mp1[num];
		}
		cout<<endl;
	}
}