#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
int main(void)
{
	int t,m,k,i,D,E,zz,z1;
	char c[10],d[100],e[100],e1[100],z[100];
	scanf("%d",&t);
	while(t--)
	{
		D = 0;
		E = 0;
		zz = 0;
		scanf("%s %d %d",c,&m,&k);
		for(i = 0;i < 8;++i)
		{
			if(c[i] == '0')
			{
				d[D++] = '0';
				d[D++] = '0';
                d[D++] = '0';
				d[D++] = '0';
			}
			else if(c[i] == '1')
			{
				d[D++] = '0';
				d[D++] = '0';
				d[D++] = '0';
				d[D++] = '1';
			}
			else if(c[i] == '2')
			{
				d[D++] = '0';
				d[D++] = '0';
				d[D++] = '1';
				d[D++] = '0';
			}
			else if(c[i] == '3')
			{
				d[D++] = '0';
				d[D++] = '0';
				d[D++] = '1';
				d[D++] = '1';
			}
			else if(c[i] == '4')
			{
				d[D++] = '0';
				d[D++] = '1';
				d[D++] = '0';
				d[D++] = '0';
			}
			else if(c[i] == '5')
			{
				d[D++] = '0';
				d[D++] = '1';
				d[D++] = '0';
				d[D++] = '1';
			}
			else if(c[i] == '6')
			{
				d[D++] = '0';
				d[D++] = '1';
				d[D++] = '1';
				d[D++] = '0';
			}
			else if(c[i] == '7')
			{
				d[D++] = '0';
				d[D++] = '1';
				d[D++] = '1';
				d[D++] = '1';
			}
			else if(c[i] == '8')
			{
				d[D++] = '1';
				d[D++] = '0';
				d[D++] = '0';
				d[D++] = '0';
			}
			else if(c[i] == '9')
			{
				d[D++] = '1';
				d[D++] = '0';
				d[D++] = '0';
				d[D++] = '1';
			}
			else if(c[i] == 'a')
			{
				d[D++] = '1';
				d[D++] = '0';
				d[D++] = '1';
				d[D++] = '0';
			}
			else if(c[i] == 'b')
			{
				d[D++] = '1';
				d[D++] = '0';
				d[D++] = '1';
				d[D++] = '1';
			}
			else if(c[i] == 'c')
			{
				d[D++] = '1';
				d[D++] = '1';
				d[D++] = '0';
				d[D++] = '0';
			}
			else if(c[i] == 'd')
			{
				d[D++] = '1';
				d[D++] = '1';
				d[D++] = '0';
				d[D++] = '1';
			}
			else if(c[i] == 'e')
			{
				d[D++] = '1';
				d[D++] = '1';
				d[D++] = '1';
				d[D++] = '0';
			}
			else if(c[i] == 'f')
			{
				d[D++] = '1';
				d[D++] = '1';
				d[D++] = '1';
				d[D++] = '1';
			}
		}
		d[D] = '\0';

		

		while(k > 0)
		{
			e[E++] = k % 2 + '0';
			k /= 2;
		}
		e[E] = '\0';

		

		for(i = 0;i < E;++i)
		{
			e1[E - 1 - i] = e[i];
		}
		e1[E] = '\0';

		

		for(i = 0;i < m;++i)
		{
			if(E < m)
			{
				d[i] = '0';
				++E;
			}
			else
			{
				d[i] = e1[zz++];
			}
		}

		//z1 = (d[4] - '0') * 8 + (d[5] - '0') * 4 + (d[6] - '0') * 2 + d[7] - '0';
		//printf("%d\n",z1);

		for(i = 0;i < 32;i += 4)
		{
			z1 = (d[i] - '0') * 8 + (d[i+1] - '0') * 4 + (d[i+2] - '0') * 2 + d[i+3] - '0';
			if(z1 == 10)
			{
				printf("a");
			}
			else if(z1 == 11)
			{
				printf("b");
			}
			else if(z1 == 12)
			{
				printf("c");
			}
			else if(z1 == 13)
			{
				printf("d");
			}
			else if(z1 == 14)
			{
				printf("e");
			}
			else if(z1 == 15)
			{
				printf("f");
			}
			else
			{
				printf("%d",z1);
			}
		}
		printf("\n");
	}
	return 0;
}