#include <iostream>
using namespace std;
int nwd( int a, int b){
if ( b== 0)
return a;
return nwd(b, a%b);
}
int main() {
int ilosc, i, n, s, pom;
for(i=0;i<ilosc;++i){
cin>>n>>s;
s%=n;
if(s==0){
cout << 0 << '\n';
}
pom = n*s/nwd(n,s);
cout << pom/s << '\n';
}
return 0;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgoKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCgppbnQgbndkKCBpbnQgYSwgaW50IGIpewogICBpZiAoIGI9PSAwKQogICAgICAgIHJldHVybiBhOwogICByZXR1cm4gbndkKGIsIGElYik7Cgp9CgppbnQgbWFpbigpIHsKICAgIGludCBpbG9zYywgaSwgbiwgcywgcG9tOwoKICAgIGZvcihpPTA7aTxpbG9zYzsrK2kpewogICAgICAgIGNpbj4+bj4+czsKICAgICAgICBzJT1uOwogICAgICAgIGlmKHM9PTApewpjb3V0IDw8IDAgPDwgJ1xuJzsKfQogICAgCiAgICAgICBwb20gPSBuKnMvbndkKG4scyk7CiAgICAgICBjb3V0IDw8IHBvbS9zIDw8ICdcbic7CgogICAgfQoKCQoJcmV0dXJuIDA7Cn0K