71

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD = 998244353;

map<ll, ll> memo_F, memo_S;

ll F(ll n) {
    if (n == 0) return 0;
    if (n == 1) return 1;
    if (memo_F.find(n) != memo_F.end()) return memo_F[n];
    ll m1 = (n - 1) / 2;
    ll m2 = n / 2;
    ll res = (n % MOD + F(m1) + F(m2)) % MOD;
    memo_F[n] = res;
    return res;
}

ll S(ll n) {
    if (n == 0) return 0;
    if (memo_S.find(n) != memo_S.end()) return memo_S[n];
    if (n == 1) return 1;
    ll m = n / 2;
    ll res;
    if (n % 2 == 0) {
        ll part1 = (m % MOD) * ((2 * m + 1) % MOD) % MOD;
        ll part2 = 4 * S(m) % MOD;
        ll part3 = 3 * F(m) % MOD;
        res = (part1 + part2 - part3) % MOD;
    } else {
        ll part1 = ((2 * m + 1) % MOD) * ((m + 1) % MOD) % MOD;
        ll part2 = 4 * S(m) % MOD;
        ll part3 = F(m) % MOD;
        res = (part1 + part2 - part3) % MOD;
    }
    if (res < 0) res += MOD;
    memo_S[n] = res;
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T;
    cin >> T;
    while (T--) {
        ll L, R;
        cin >> L >> R;
        ll ans = (S(R) - S(L - 1)) % MOD;
        if (ans < 0) ans += MOD;
        cout << ans << '\n';
    }
    return 0;
}