#include <iostream>
using namespace std;
int main(){
    int n, a, b;
    cin >> n;
    int t[n];
    for (int i=0; i<n; i++){
            cin >> a >> b;
            if (a==b)
                t[i]=a+b;
            else{
                while (a!=b){
                        if (a<b)
                        b-=a;
                        else
                        a-=b;
                }
                t[i]=a+b;
            }
 
    }
    for (int i=0; i<n; i++)
        cout << t[i] << endl;
    return 0;
}

I2luY2x1ZGUgPGlvc3RyZWFtPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwppbnQgbWFpbigpewogICAgaW50IG4sIGEsIGI7CiAgICBjaW4gPj4gbjsKICAgIGludCB0W25dOwogICAgZm9yIChpbnQgaT0wOyBpPG47IGkrKyl7CiAgICAgICAgICAgIGNpbiA+PiBhID4+IGI7CiAgICAgICAgICAgIGlmIChhPT1iKQogICAgICAgICAgICAgICAgdFtpXT1hK2I7CiAgICAgICAgICAgIGVsc2V7CiAgICAgICAgICAgICAgICB3aGlsZSAoYSE9Yil7CiAgICAgICAgICAgICAgICAgICAgICAgIGlmIChhPGIpCiAgICAgICAgICAgICAgICAgICAgICAgIGItPWE7CiAgICAgICAgICAgICAgICAgICAgICAgIGVsc2UKICAgICAgICAgICAgICAgICAgICAgICAgYS09YjsKICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICAgIHRbaV09YStiOwogICAgICAgICAgICB9CgogICAgfQogICAgZm9yIChpbnQgaT0wOyBpPG47IGkrKykKICAgICAgICBjb3V0IDw8IHRbaV0gPDwgZW5kbDsKICAgIHJldHVybiAwOwp9

MwoxIDEKMTIzIDEyMzQ1CjkgNg==

3
1 1
123 12345
9 6