#include <bits/stdc++.h>

using namespace std;

long long g(long long x, long long y) {
    long long res = 0;
    while (x != 1) {
        long long v = (x + y - 1) / y, t = min((x - ((v - 1) * y)) / v + 1, (x - 1) / v);
        x -= v * t;
        res += t;
    }
    return res;
}

long long f(long long x, long long y) {
    --x;
    long long res = 1;
    while (y) {
        long long v = (res + x - 1) / x, t = min((x * v - res) / v + 1, y);
        res += v * t;
        y -= t;
    }
    return res;
}

signed main() {
    int T; scanf("%d", &T);
    while (T--) {
        long long n, m; scanf("%lld%lld", &n, &m);
        printf("%lld\n", f(m, g(n, m)));
    }
    return 0;
}