import java.util.Scanner;

public class Main {

    static final String[] hx = {"0000", "0001", "0010", "0011", "0100", "0101", "0110", "0111", "1000", "1001", "1010", "1011", "1100", "1101", "1110", "1111"};

    public static void main(String[] args) {
        int amount;
        Scanner in = new Scanner(System.in);
        amount = in.nextInt();
        for (int i = 0; i < amount; i++) {
            int m, k;
            String str;
            str = in.next();
            m = in.nextInt();
            k = in.nextInt();
            String later = String.format("%" + m + "s", Integer.toBinaryString(k)).replace(' ', '0');
            StringBuilder stringBuilder = new StringBuilder(transStr(str));
            stringBuilder.replace(0, m, later);
            StringBuilder result = new StringBuilder("");
            for (int j = 0; j < stringBuilder.length(); j +=4) {
                result.append(Integer.toHexString(Integer.valueOf(stringBuilder.substring(j, j + 4),2)));
            }
            System.out.println(result);
        }
    }

    private static String transStr(String str) {
        StringBuilder res = new StringBuilder("");
        for (int i = 0; i < str.length(); i++) {
            char a = str.charAt(i);
            if (a >= 'a') {
                res.append(hx[a - 'a' + 10]);
            }
            else {
                res.append(hx[a - '0']);
            }
        }
        return res.toString();
    }
}