N  ,  M  ,  K  ,  gcd(a,b)=1

N,M can be written as
N = a + b
M = a^2 + b^2 - (2^K - 2) * a * b

Note: a,b are not given
N ,M ~ 10^400

#include <cstdio>
#include <cstring>
using namespace std;

bool mod(const char *str,int num) //check if str%num==0
{
	int i,len=strlen(str),res=0;
	
	for(i=0;i<len;i++)
	{
		res=10*res+str[i]-'0';
		res%=num;
	}
	return res==0;
}

int main()
{
	int cases,K,gcd,temp;
	char N[1005],M[1005];
	
	
	scanf("%d",&cases);
	while(cases--)
	{
		scanf("%s %s %d",N,M,&K);
		
		gcd=1;
		temp=1;
		
		while(1)
		{
			if(mod(N,temp) && mod(M,temp))gcd=temp;
			else break;	
			temp*=2;
		}
		printf("%d\n",gcd);
	}
	return 0;
}