#include<stdio.h>
#include<string.h>
int main() {
	int t, d;
	long long m, k;
	char str[1000];
	int sum[1000], sum2[1000], sum3[10000], sum4[10000], ans[1000];
	scanf("%d", &t);
	getchar();
	while (t--) {
		d = 0;
		memset(sum2, 0, sizeof sum2);
		memset(sum3, 0, sizeof sum3);
		memset(ans, 0, sizeof ans);
		scanf("%s", str);
		scanf("%lld%lld", &m, &k);
		int f = m;
		int len = strlen(str);
		for (int i = 0; i < len; i++) {
			if (str[i] >= 'a') sum[i] = str[i] - 87;
			if (str[i] <= '9') sum[i] = str[i] - 48;
		}
		while (k != 0) {
			sum2[m--] = k % 2;
			k /= 2;
		}
		for (int i = 0; i < len; i++) {
			int len = (i + 1) * 4;
			while (sum[i] != 0) {
				sum3[len--] = sum[i] % 2;
				sum[i] /= 2;
			}
		}
		for (int i = 1; i <= len * 4; i++) {
			if (i <= f) sum4[i] = sum2[i];
			else sum4[i] = sum3[i];
		}
		int ansl = 0;
		for (int i = 1; i <= len * 4; i += 4) {
			ans[++ansl] += sum4[i+3] + sum4[i+2] * 2 + sum4[i+1] * 4 + sum4[i] * 8;
		}
		for (int i = 1; i <= ansl; i++) {
			if (ans[i] >= 10) printf("%c", ans[i] + 87);
			else printf("%d", ans[i]);
		}
		printf("\n");
	}
}