//http://www.codechef.com/problems/GCD2/
#include<stdio.h>
unsigned int gcd(unsigned int a,unsigned int b)
{
if(b==0) return a;
else return(gcd(b,a%b));
}
void print(int a[],int len)
{
int i;
for(i=0;i<len;i++)
printf("%d",a[i]);
printf("\n");
}
main()
{
int t,length,i,j;
int a[251];
unsigned int b;
char c;
scanf("%d",&t);
while(t–)
{
scanf("%u",&b);
getchar();
length=0;
while((c=getchar())!='\n')
{
a[length++]=c-'0';
}//Input a while
if(b==0){
//printf("detected");
print(a,length);
continue;
}
unsigned int num=a[0];
int length2=1;
while(num<b){
num = num*10+a[length2++];
}
//calculating a%b in first case
num = num%b;
while(length2<length)
{
num = num*10+a[length2++];
num = num % b;
}
//printf("%u\n",num);
printf("%d\n",gcd(b,num));
}
}