#include<bits/stdc++.h>
#define LL __int128
using namespace std;
LL gcd(LL x,LL y){return y?gcd(y,x%y):x;}
LL sol(LL l,LL m,LL k){
    LL d=gcd(m,k);
    if (d==1) return l;
    if (l>k/d) return m*(k-l)/d+sol((k-m*(k-l))/d,m,k/d);
    return l;
}
int T;LL m,k;
signed main () {
    scanf("%d",&T);
    while (T--) {
        scanf("%lld %lld",&m,&k);
        printf("%lld\n",sol(k-1,m,k)+1);
    } return 0;
}

  我们发现自动机的平凡上界就是T。

   因为我们令到每一个点的路径在mo T意义下相等，则这样一定是合法的。

  我们考虑如何合并这些点：

  我们发现在 当两个点可以到达的点是一致的时候，就可以缩为一个点。

  我们发现*k mo T 相同就可以缩点。

  我们发现这样子是过不了的。

   因为我们其实缩点以后，我们划归为了一个子问题，所以我们要迭代下去。

   我们怎么迭代呢，我们考虑缩点以后用标号小的点来表示新点

   那我们发现每次后，剩下的0 到 X 联续的。

  我们可以每次拿掉一个 gcd 迭代。

  终止条件是 X与 T（迭代后的）互质。

 这样做的正确性比较显然吧。

  考试的时候simple的认为这是数论相关的。应该会带个u ，默默的减去 平方因子的贡献，非常神奇的是，过了大样例。然后华丽爆零
#include<bits/stdc++.h>
#define LL __int128
using namespace std;
LL gcd(LL x,LL y){return y?gcd(y,x%y):x;}
LL sol(LL l,LL m,LL k){
    LL d=gcd(m,k);
    if (d==1) return l;
    if (l>k/d) return m*(k-l)/d+sol((k-m*(k-l))/d,m,k/d);
    return l;
}
int T;LL m,k;
signed main () {
    scanf("%d",&T);
    while (T--) {
        scanf("%lld %lld",&m,&k);
        printf("%lld\n",sol(k-1,m,k)+1);
    } return 0;
}