import java.util.Scanner;

public class Main {
	public int power(int a, int b) {
		int rs=1;
		for(int i=0; i<b; i++) {
			rs*=a;
		}
		return rs;
	}
	public void hexToBin(String a, int[] b) {
		int k=0;
		for(int i=0; i<a.length(); i++) {
			int num = a.charAt(i) - '0' > 9 ? 10 + a.charAt(i) - 'a' : a.charAt(i) - '0';
			String n = Integer.toBinaryString(num);
			for(int j=0; j<4; j++) {
				if(j<4-n.length()) b[k++]=0;
				else b[k++] = n.charAt(j-(4-n.length()))-'0';
			}
		}
	}
	
	public void replace(int m, int k, int[] b) {
		String n = Integer.toBinaryString(k);
		for(int i=0; i<m; i++) {
			if(i<m-n.length()) b[i]=0;
			else b[i]=n.charAt(i-(m-n.length()))-'0';
		}
	}
	
	public StringBuilder binToHex(int[] b) {
		StringBuilder c= new StringBuilder("");
		for(int i=0; i<8; i++) {
			int sum=0;
			for(int j=4*i+3; j>=4*i; j--) {
				sum=sum+power(2,4*i+3-j)*b[j];
			}
			char ch = sum > 9 ? (char)('a' + sum - 10) : (char)('0' + sum);
			c.append(ch);
		}
		return c;
	}
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		Main main = new Main();
		int T = in.nextInt();
		String a;                  
		int[] b = new int[32];		//存放2进制的数据
		
		int m,k;
		for(int i=0; i<T; i++) {
			a = in.next();
			m = in.nextInt();
			k = in.nextInt();
			
			main.hexToBin(a, b);
			main.replace(m, k, b);
			System.out.println(main.binToHex(b).toString());
			
		}
	}
	
}