#include<iostream>
#include<string>
#include<cstdio>
#include<iomanip>
#include<cctype>
#include<cmath>
#include<map>
#include<algorithm>
using namespace std;
map<char, string> yz;
map<string, char> hh;
int gcd(int x, int y) {
	if(x < 0)
		x = -x;
	if(y < 0)
		y = -y;
	if(x == 0)
		return 1;
	int r = x % y;
	while(r) {
		x = y;
		y = r;
		r = x % y;
	}
	return y;
}
int main() {
	yz['0'] = "0000";
	yz['1'] = "0001";
	yz['2'] = "0010";
	yz['3'] = "0011";
	yz['4'] = "0100";
	yz['5'] = "0101";
	yz['6'] = "0110";
	yz['7'] = "0111";
	yz['8'] = "1000";
	yz['9'] = "1001";
	yz['a'] = "1010";
	yz['b'] = "1011";
	yz['c'] = "1100";
	yz['d'] = "1101";
	yz['e'] = "1110";
	yz['f'] = "1111";
	hh["0000"] = '0';
	hh["0001"] = '1';
	hh["0010"] = '2';
	hh["0011"] = '3';
	hh["0100"] = '4';
	hh["0101"] = '5';
	hh["0110"] = '6';
	hh["0111"] = '7';
	hh["1000"] = '8';
	hh["1001"] = '9';
	hh["1010"] = 'a';
	hh["1011"] = 'b';
	hh["1100"] = 'c';
	hh["1101"] = 'd';
	hh["1110"] = 'e';
	hh["1111"] = 'f';
	int t;
	cin >> t;
	string m, n, tt;
	int i, j, flag, value;
	while(t--) {
		cin >> m;
		n = "";
		tt = "";
		string zz = "";
		for(i = 0; i < m.size(); i++) {
			n += yz[m[i]];
		}
		cin >> flag;
		cin >> value;
		int r;
		int m = flag;
		while(m--) {
			r = value % 2;
			if(r == 0)
				tt += "0";
			else
				tt += "1";
			value /= 2;
		}
		reverse(tt.begin(),tt.end());
		while(tt.size() != flag) {
			tt += "0";
		}

		for(i = 0; i < tt.size(); i++) {
			n[i] = tt[i];
		}
		for(i = 0; i < n.size(); i++) {
			zz += n[i];
			if(i % 4 == 3){
				cout << hh[zz];
				zz = "";
			}
		}
		if(t != 0)
			cout << endl;
	}
	return 0;
}