#include <iostream>
using namespace std;
int a,b,testy;
int main()
{
cin>>testy;
for (int i=0; i<testy; i++)
{
cin>>a>>b;
while (a!=b)
{
if (a<b) b=b-a;
else if (b<a) a=a-b;
}
cout<<a+b;
a=0; b=0;
}
return 0;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgoKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCmludCBhLGIsdGVzdHk7CgppbnQgbWFpbigpCnsKICAgIGNpbj4+dGVzdHk7CgogICAgZm9yIChpbnQgaT0wOyBpPHRlc3R5OyBpKyspCiAgICB7CiAgICAgICAgY2luPj5hPj5iOwoKICAgICAgICB3aGlsZSAoYSE9YikKICAgICAgICB7CiAgICAgICAgICAgIGlmIChhPGIpIGI9Yi1hOwogICAgICAgICAgICBlbHNlIGlmIChiPGEpIGE9YS1iOwogICAgICAgIH0KICAgICAgICBjb3V0PDxhK2I7CgogICAgICAgIGE9MDsgYj0wOwogICAgfQoKICAgIHJldHVybiAwOwp9Cg==