#include<iostream>
#include<string>
#include<cstdio>
#include<algorithm>
using namespace std;

bool cmp1(int a,int b)
{
	return a>b;
}

int main()
{
	string str_b[16]={"0000","0001","0010","0011","0100","0101","0110","0111","1000","1001","1010","1011","1100","1101","1110","1111"};
	int t;
	cin >> t;
	while (t--)
	{
		string str1,k_b,ans;
		int m,k;
		cin >> str1 >> m >> k;
		while(k>0)
		{
			k_b.push_back('0'+k%2);
			k/=2;
		}
		while(k_b.size()<m)
			k_b.push_back('0');
		for(int i=0;i<str1.size();i++)
		{
			if(str1[i]<='9'&&str1[i]>='0')
				ans+=str_b[str1[i]-'0'];
			else
				ans+=str_b[str1[i]-'a'+10];
		}
		for(int i=0;i<m;i++)
		{
				ans[i]=k_b[k_b.size()-i-1];
		}
		for (int i=0;i<ans.size();i+=4)
		{
			int temp=(ans[i]-'0')*8+(ans[i+1]-'0')*4+(ans[i+2]-'0')*2+(ans[i+3]-'0');
			if (temp>9)
			{
				char c='a'+temp-10;
				cout << c;
			}
			else
				cout << temp;
		}
		cout << endl;
	}
	return 0;
}