#include<bits/stdc++.h>
typedef __int128 iint;
using namespace std;
iint m;
iint gcd(iint a, iint b) {
if (b == 0) return a;
return gcd(b, a % b);
}
iint calc(iint h, iint d, iint k) {
if (h <= 0) return 0;
iint g = gcd(m, k), k0 = k / g, m0 = m / g;
if (g == 1) return 0;
if (h <= k0) return 0;
d *= m0;
return h - k0 + calc(k0 - d, d, k0);
}
int main() {
int T; scanf("%d", &T);
while (T--) {
long long m_, k_; scanf("%lld%lld", &m_, &k_);
m = m_;
printf("%lld\n", k_ - (long long)calc(k_ - 1, 1, k_));
}
}
