#include<stdio.h>
#include<string.h> 
#include<math.h>
void ts(long long variable,int * ch){
	int i,j;
	int str[32];
	for (int index=0;index<32;index++)
      {
        i=variable%2;  
        j=variable/2;  
        variable=j;   
        str[index]=i;               
      }
      for(i=0;i<32;++i){
      	ch[i]=str[31-i];
	  }
}
long long g(int a,int b){
	long  long sum=1;
	if(a==0)	return 1;
	else{
		for(int i=0;i<a;++i)
			sum*=b; 
	}
	return sum;
}
long long f(){
	char ch[9];
	long long sum=0;
	gets(ch);
	for(int i =7;i>=0;--i){
	if(ch[i]>='0'&&ch[i]<='9')
	sum+=(ch[i]-'0')*g(7-i,16);
	else if(ch[i]>='a'&&ch[i]<='f')
	sum+=(ch[i]-'a'+10)*g(7-i,16);
	}
	return sum;
}

int main(){
	int T;
	scanf("%d",&T);
	getchar();
	while(T--){
		
		long long int sum = f();
		int a,b;
		scanf("%d",&a);
		getchar();
		scanf("%d",&b);
		getchar();
		int num1[32]={0},num2[32]={0};
		ts(b,num1);
		ts(sum,num2);
		for(int i=32-a,j=0;i<32;++i,++j)
			num2[j]=num1[i];
		long long sum2 = 0;
		for(int i=0;i<32;++i){
			sum2+=num2[i]*g(31-i,2);
		}
		printf("%08llx\n",sum2);
		
		
		
		
		
	}

		

}