C++ :

#include <bits/stdc++.h>
#define LLL __int128
#define LL long long
using namespace std;

int T;
LL K, m;

LL Gcd(LL x, LL y) {
  return !y ? x : Gcd(y, x % y);
}

LL Solve(LL L, LL m, LL K, LL las) {
  LL d = Gcd(K, las);
  if(L <= K / d) return L;
  if((LLL)K - (LLL)m * (K - L) <= 0) return K / d;
  return m * (K - L) / d + Solve((K - m * (K - L)) / d, m, K / d, d);
}

int main(void) {
  scanf("%d", &T);
  while(T--) {
    scanf("%lld%lld", &m, &K);
    printf("%lld\n", Solve(K - 1, m, K, m) + 1);
  }
  return 0;
}