#include<stdio.h> 
#include<string.h> 
int main(void){ 
    char a[8]; 
    int n,m,k; 
    scanf("%d",&n); 
    while(n--){ 
        int sec[8][4]={0},b[8]; 
        scanf("%s",a); 
        scanf("%d%d",&m,&k); 
        getchar(); 
        for(int i=0;i<8;i++){ 
            if(a[i] >= 'a' &&a[i] <= 'f'){ b[i] = a[i]-87; 
                
            } 
            else{ b[i] = a[i]-48; } if(b[i] % 2 == 1) sec[i][3] = 1; 
            if(b[i]/2%2 == 1) sec[i][2] = 1; 
            if(b[i]/4%2==1) sec[i][1] = 1; 
            if(b[i] >= 8) sec[i][0] = 1; 
            
        } 
        int secd[m];
        for(int i = 0;i <m;i++){ secd[i] = 0;
        } 
        for(int i = 1;i <= m,k!=0;i++){ 
            secd[m-i] = k%2; k/=2; } 
            for(int i = 0;i < m;i++){ *(*sec+i) = secd[i];
            } 
            for(int i = 0;i < 8;i ++){
                int s = 8*sec[i][0] + 4*sec[i][1] + 2*sec[i][2] + sec[i][3]; 
                if(s >= 0 &&s <= 9)
                printf("%d",s); 
                else if(s >= 10 && s <= 15) printf("%c",s-10 + 'a');
                }
                printf("\n");
                } 
                return 0;
                }