#include <iostream>
using namespace std;
int t, a, b;
int main()
{
cin >> t;
for (int i=0; i<t; i++)
{
cin >> a >> b;
while (a>b)
{
a = a-b;
}
while (b>a)
{
b = b-a;
}
cout <<a+b;
}
}
I2luY2x1ZGUgPGlvc3RyZWFtPgoKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKaW50IHQsIGEsIGI7CmludCBtYWluKCkKewogICAgY2luID4+IHQ7CiAgICBmb3IgKGludCBpPTA7IGk8dDsgaSsrKQogICAgewogICAgICAgIGNpbiA+PiBhID4+IGI7CiAgICAgICAgd2hpbGUgKGE+YikKICAgICAgICB7CiAgICAgICAgICAgIGEgPSBhLWI7CiAgICAgICAgfQogICAgICAgIHdoaWxlIChiPmEpCiAgICAgICAgewogICAgICAgICAgICBiID0gYi1hOwogICAgICAgIH0KICAgICAgICBjb3V0IDw8YStiOwoKICAgIH0KfQ==