#include <stdio.h>
int main()
{
    int t,m,k,i,j,g;
    char a[10],b[40],c[40];
    scanf("%d",&t);
    while(t--){
               getchar();
               scanf("%s %d %d",&a,&m,&k);
                for(i=0;i<8;i++){
                                 if(a[i]=='a') a[i]=10;
                                 else if(a[i]=='b') a[i]=11;
                                 else if(a[i]=='c') a[i]=12;
                                 else if(a[i]=='d') a[i]=13;
                                 else if(a[i]=='e') a[i]=14;
                                 else if(a[i]=='f') a[i]=15;   
                                 b[4*i+3]=a[i]%2;a[i]/=2;
                                 b[4*i+2]=a[i]%2;a[i]/=2;  
                                 b[4*i+1]=a[i]%2;a[i]/=2;
                                 b[4*i]=a[i]%2;
                }
                i=0;
                while(k){
                  c[i]=k%2;
                  i++;
                  k/=2;       
                }
                for(j=0;j<i;j++){
                                 b[m-j-1]=c[j];
                }
                for(i=m-j-1;i>=0;i--) b[i]=0;
                for(i=0;i<8;i++){
                                 a[i]=b[4*i]*2*2*2+b[4*i+1]*2*2+b[4*i+2]*2+b[4*i+3];
                                 printf("%x",a[i]);
                                 }
                                 printf("\n");
    }
}