1#include<stdio.h>
2char b[300];
3int rem(int a) {
4 int p=0,i;
5 for(i=0;b[i]!= '\0';i++) p = ((b[i]-'0')+p*10) %a;
6 return p;
7}
8
9int gcd(int a,int b) {
10 if(b==0) return a;
11 else gcd(b,a%b);
12}
13
14int main() {
15 int i,j,a;
16 scanf("%d",&i);
17 while(i--) {
18 scanf("%d %s",&a,b);
19 if(a == 0) printf("%s\n",b);
20 else {
21 int p = rem(a);
22 printf("%d\n",gcd(a,p));
23 }
24 }
25 return 0;
26}
27