#include<cstdlib>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
char c;
int l,n,ans,m,p,k,ll;
char s[100];
int b[10100];
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
      {
      getchar();
      memset(b,0,sizeof(b));
      gets(s);ll=strlen(s);
      for(int i=0;i<ll;i++) 
          {
          if(s[i]>='0'&&s[i]<='9') p=s[i]-'0';
             else p=s[i]-'a'+10;
           l=(i+1)*4;
               while (p>0)
                 {
                     b[l]=p%2;
                     p/=2;
                     l--;
                 }
          }
      scanf("%d%d",&m,&k);p=m;
      for(int i=1;i<=m;i++) b[i]=0;
      while (k>0)
        {
            b[p]=k%2;
            k/=2;
            p--;
        }
      for(int i=0;i<ll;i++)
         {
           p=1;l=(i+1)*4;ans=0;
           while (l!=i*4)
             {
             ans+=p*b[l];
             p*=2;l--;
             }    
           if(ans>=10) ans=ans+87;
                  else ans=ans+48;
           c=ans;
           printf("%c",c);
         }
      printf("\n");
      }
}