#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==