/*
f(a, b, c, n) = \sum_{i = 0}^n\lfloor\frac{ai + b}{c}\rfloor
$O(\log n)$
*/
#include <bits/stdc++.h>
using namespace std;
using LL = long long;

// 注意以下计算 x 取值是 (0, n]，即不包括 0
// 特别注意的是这里的 a, b, n 不能提前模（有向下取整）！
template <class Info>
struct floorSum {
    LL a, b, c, n;
    Info u, r;
    floorSum(LL a, LL b, LL c, LL n, Info u, Info r) : a(a), b(b), c(c), n(n), u(u), r(r) {}

    Info qpow(Info a, LL b) {
        Info res(1);
        while (b) {
            if (b & 1) {
                res = res + a;
            }
            b >>= 1;
            a = a + a;
        }
        return res;
    }

    Info operator()() {
        if (n <= 0) {
            return Info(1);
        }
        return qpow(u, b / c) + solve(a, b % c, c, n, u, r);
    }

    LL calc(const LL &a, const LL &b, const LL &c, const LL &x) { return (__int128(a) * x + b) / c; }

    Info solve(LL a, LL b, LL c, LL n, Info u, Info r) {
        if (n == 0) {
            return Info(1);
        }
        if (a >= c) {
            return solve(a % c, b, c, n, u, qpow(u, a / c) + r);
        }
        LL m = calc(a, b, c, n);
        if (m == 0) {
            return qpow(r, n);
        }
        LL cnt = n - calc(m, -b - 1, a, c);
        return qpow(r, (c - b - 1) / a) + u + solve(c, (c - b - 1) % a, a, m - 1, r, u) + qpow(r, cnt);
    }
};

constexpr LL MOD = 998244353;
struct Info : array<array<LL, 3>, 3> {
    Info(int x = 0) : array<array<LL, 3>, 3>{} {
        for (int i = 0; i < 3; ++i) {
            (*this)[i][i] = x;
        }
    }
};

Info operator+(const Info &a, const Info &b) {
    Info c;
    for (int i = 0; i < 3; ++i) {
        for (int j = 0; j < 3; ++j) {
            for (int k = 0; k < 3; ++k) {
                (c[i][j] += a[i][k] * b[k][j] % MOD) %= MOD;
            }
        }
    }
    return c;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T;
    cin >> T;
    while (T--) {
        LL a, b;
        cin >> a >> b;
        Info u, r, s, t;

        u[0][0] = u[1][0] = u[1][1] = u[2][0] = u[2][2] = 1;

        r[0][0] = r[0][1] = r[1][1] = r[2][1] = r[2][2] = 1;

        s[0][2] = 1;
        s = s + u + r;
        t[0][0] = 2;
        t[0][1] = -1;
        t[0][2] = 0;
        t[1][0] = -1;
        t[1][1] = 1;
        t[1][2] = 0;
        t[2][0] = 0;
        t[2][1] = -1;
        t[2][2] = 1;

        auto ans = s + floorSum<Info>(a, 0, b, b, u, r)() + t;
        cout << ((ans[0][0] + ans[0][1] + 1) % MOD + MOD) % MOD << '\n';
    }
    return 0;
}

/*
18
5 9
23 30
820 483
5739 9232
86494 55350
606 13336
2768848 1124639
47995594 66053082
1069395 7177
7801842511 4390103762
47882886553 82678306054
193410894 6189355686
51594638 19992922190
59 110
422735115778072 658356435030265
9125338158530266 5328357177709583
60743352262021049 95595862538791630
629312141725417942 999581828389011547
*/