#include <iostream>
#include <string>
using namespace std;
string to_second(int ch, int ws) {
	string a = "";
	while (ch > 0) {
		a.insert(0, 1, ch % 2 + '0');
		ch /= 2;
	}
	while (a.size() < ws) a.insert(0, 1, '0');
	return a;
}
char to_char(string str) {
	char ji ;
	int temp = (str[0]-'0') * 8 + (str[1]-'0') * 4 + (str[2]-'0') * 2 + str[3]-'0';
	if (temp > 9) ji = temp - 10 + 'a';
	else ji = temp + '0';
	return ji;
}
int main () {
	int t, m, k;
	cin >> t;
	while (t--) {
		string temp, save = "", out = "";
		cin >> temp >> m >> k;
		for (int i = 0; i < temp.size(); i++) {
			int t;
			if (temp[i] >= 'a') t = temp[i] - 'a' + 10;
			else t = temp[i] - '0';
			save += to_second(t, 4);
		}
		string rep = to_second(k, m);
		for (int i = 0; i < m; i++) save[i] = rep[i];
		for (int i = 0; i < save.size(); i += 4) {
			string z = save.substr(i, 4);
			out.push_back(to_char(z));
		}
		cout << out << endl;
	}
}