#include <iostream>
#include <cstring>
using namespace std;
char arr[255];
int mod(int a) {
int c=0;
for(int i=0; i<strlen(arr); i++) c=((arr[i]-'0')+c*10)%a;
return c;
}
int gcd(int a, int b) {
if(b==0) return a;
else return gcd(b, a%b);
}
int main() {
// your code goes here
int n, a;
cin>>n;
while(n--) {
cin>>a>>arr;
if(a==0) cout<<arr<<endl;
else {
int d=mod(a);
cout<<gcd(a, d)<<endl;
}
}
return 0;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8Y3N0cmluZz4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCmNoYXIgYXJyWzI1NV07CgppbnQgbW9kKGludCBhKSB7CglpbnQgYz0wOwoJZm9yKGludCBpPTA7IGk8c3RybGVuKGFycik7IGkrKykgYz0oKGFycltpXS0nMCcpK2MqMTApJWE7IAoJcmV0dXJuIGM7Cgl9CgkKaW50IGdjZChpbnQgYSwgaW50IGIpIHsKCWlmKGI9PTApIHJldHVybiBhOwoJZWxzZSByZXR1cm4gZ2NkKGIsIGElYik7Cn0KCmludCBtYWluKCkgewoJLy8geW91ciBjb2RlIGdvZXMgaGVyZQoJaW50IG4sIGE7CgljaW4+Pm47Cgl3aGlsZShuLS0pIHsKCQljaW4+PmE+PmFycjsKCQlpZihhPT0wKSBjb3V0PDxhcnI8PGVuZGw7CgkJZWxzZSB7CgkJCWludCBkPW1vZChhKTsKCQkJY291dDw8Z2NkKGEsIGQpPDxlbmRsOwoJCX0KCX0KCXJldHVybiAwOwp9