#include <iostream>
#include <string>
#include <sstream>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <numeric>
 
using namespace std;
 
vector <int> czynniki_pierwsze(int x){
    vector <int> result;
    for(int i=2;i<=x;i++){
        if(x%i == 0){
            result.push_back(i);
            x=x/i;
            i--;
        }
    }
    return result;
}
 
int wspolny_czynnik(vector <int> x, vector <int> y){
    vector <int> result;
    vector <int> bigger;
    vector <int> smaller;
    if(x.size() > y.size()){
        bigger = x;
        smaller = y;
    }
    else{
        bigger = y;
        smaller = x;
    }
 
    for(int i=0; i<bigger.size(); i++) {
        result.push_back(bigger[i]);
    }
    for(int k=0; k<smaller.size(); k++) {
        vector <int>::iterator it = find(bigger.begin(), bigger.end(), smaller[k]);
        if(it == bigger.end()){
            result.push_back(smaller[k]);
        }
    }
    int wynik = std::accumulate(result.begin(), result.end(), 1, std::multiplies<int>());
    return wynik;
 
}
 
int main(){
 
    int n;
    cin >> n;
    while(n > 0){
        int a, b;
        cin >> a;
        cin >> b;
        vector <int> czynniki_a = czynniki_pierwsze(a);
        vector <int> czynniki_b = czynniki_pierwsze(b);
        int nwc = wspolny_czynnik(czynniki_a, czynniki_b);
        cout << nwc << endl;
        n--;
    }
    return 0;
}
 

I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8c3RyaW5nPgojaW5jbHVkZSA8c3N0cmVhbT4KI2luY2x1ZGUgPGNtYXRoPgojaW5jbHVkZSA8Y3N0ZGxpYj4KI2luY2x1ZGUgPGFsZ29yaXRobT4KI2luY2x1ZGUgPHZlY3Rvcj4KI2luY2x1ZGUgPG51bWVyaWM+Cgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKdmVjdG9yIDxpbnQ+IGN6eW5uaWtpX3BpZXJ3c3plKGludCB4KXsKICAgIHZlY3RvciA8aW50PiByZXN1bHQ7CiAgICBmb3IoaW50IGk9MjtpPD14O2krKyl7CiAgICAgICAgaWYoeCVpID09IDApewogICAgICAgICAgICByZXN1bHQucHVzaF9iYWNrKGkpOwogICAgICAgICAgICB4PXgvaTsKICAgICAgICAgICAgaS0tOwogICAgICAgIH0KICAgIH0KICAgIHJldHVybiByZXN1bHQ7Cn0KCmludCB3c3BvbG55X2N6eW5uaWsodmVjdG9yIDxpbnQ+IHgsIHZlY3RvciA8aW50PiB5KXsKICAgIHZlY3RvciA8aW50PiByZXN1bHQ7CiAgICB2ZWN0b3IgPGludD4gYmlnZ2VyOwogICAgdmVjdG9yIDxpbnQ+IHNtYWxsZXI7CiAgICBpZih4LnNpemUoKSA+IHkuc2l6ZSgpKXsKICAgICAgICBiaWdnZXIgPSB4OwogICAgICAgIHNtYWxsZXIgPSB5OwogICAgfQogICAgZWxzZXsKICAgICAgICBiaWdnZXIgPSB5OwogICAgICAgIHNtYWxsZXIgPSB4OwogICAgfQoKICAgIGZvcihpbnQgaT0wOyBpPGJpZ2dlci5zaXplKCk7IGkrKykgewogICAgICAgIHJlc3VsdC5wdXNoX2JhY2soYmlnZ2VyW2ldKTsKICAgIH0KICAgIGZvcihpbnQgaz0wOyBrPHNtYWxsZXIuc2l6ZSgpOyBrKyspIHsKICAgICAgICB2ZWN0b3IgPGludD46Oml0ZXJhdG9yIGl0ID0gZmluZChiaWdnZXIuYmVnaW4oKSwgYmlnZ2VyLmVuZCgpLCBzbWFsbGVyW2tdKTsKICAgICAgICBpZihpdCA9PSBiaWdnZXIuZW5kKCkpewogICAgICAgICAgICByZXN1bHQucHVzaF9iYWNrKHNtYWxsZXJba10pOwogICAgICAgIH0KICAgIH0KICAgIGludCB3eW5payA9IHN0ZDo6YWNjdW11bGF0ZShyZXN1bHQuYmVnaW4oKSwgcmVzdWx0LmVuZCgpLCAxLCBzdGQ6Om11bHRpcGxpZXM8aW50PigpKTsKICAgIHJldHVybiB3eW5pazsKCn0KCmludCBtYWluKCl7CgogICAgaW50IG47CiAgICBjaW4gPj4gbjsKICAgIHdoaWxlKG4gPiAwKXsKICAgICAgICBpbnQgYSwgYjsKICAgICAgICBjaW4gPj4gYTsKICAgICAgICBjaW4gPj4gYjsKICAgICAgICB2ZWN0b3IgPGludD4gY3p5bm5pa2lfYSA9IGN6eW5uaWtpX3BpZXJ3c3plKGEpOwogICAgICAgIHZlY3RvciA8aW50PiBjenlubmlraV9iID0gY3p5bm5pa2lfcGllcndzemUoYik7CiAgICAgICAgaW50IG53YyA9IHdzcG9sbnlfY3p5bm5payhjenlubmlraV9hLCBjenlubmlraV9iKTsKICAgICAgICBjb3V0IDw8IG53YyA8PCBlbmRsOwogICAgICAgIG4tLTsKICAgIH0KICAgIHJldHVybiAwOwp9Cg==

OAoxMCAxMgoxMiAxNQoyMyAyNwoxOCAyMwozMCAzMAoyMCAyMAoyOSAyOQoyOCAxMg==

8
10 12
12 15
23 27
18 23
30 30
20 20
29 29
28 12