#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

template<int mod>
class Modular {
public:
    int val;
    Modular() : val(0) {}
    Modular(int new_val) : val(new_val) {}
    friend Modular operator+(const Modular& a, const Modular& b) {
        if (a.val + b.val >= mod) return a.val + b.val - mod;
        else return a.val + b.val;
    }
    friend Modular operator-(const Modular& a, const Modular& b) {
        if (a.val - b.val < 0) return a.val - b.val + mod;
        else return a.val - b.val;
    }
    friend Modular operator*(const Modular& a, const Modular& b) {
        return 1ll * a.val * b.val % mod;
    }
    friend Modular binpow(Modular a, long long n) {
        Modular res = 1;
        for (; n; n >>= 1) {
            if (n & 1) res *= a;
            a *= a;
        }
        return res;
    }
    friend Modular inv(const Modular& a) {
        return binpow(a, mod - 2);
    }
    Modular operator/(const Modular& ot) const {
        return *this * inv(ot);
    }
    Modular& operator++() {
        if (val + 1 == mod) val = 0;
        else ++val;
        return *this;
    }
    Modular operator++(int) {
        Modular tmp = *this;
        ++(*this);
        return tmp;
    }
    Modular operator+() const {
        return *this;
    }
    Modular operator-() const {
        return 0 - *this;
    }
    Modular& operator+=(const Modular& ot) {
        return *this = *this + ot;
    }
    Modular& operator-=(const Modular& ot) {
        return *this = *this - ot;
    }
    Modular& operator*=(const Modular& ot) {
        return *this = *this * ot;
    }
    Modular& operator/=(const Modular& ot) {
        return *this = *this / ot;
    }
};

template<int mod>
istream& operator>>(istream& istr, Modular<mod>& x) {
    return istr >> x.val;
}

template<int mod>
ostream& operator<<(ostream& ostr, const Modular<mod>& x) {
    return ostr << x.val;
}

const int mod = 998244353; // 998244353
using Mint = Modular<mod>;

const ll inf = 1e18;

typedef long double ld;
const ld eps = 1e-9;

ll safe_mult(ll a, ll b) {
    if (a <= inf / b) {
        return a * b;
    } else {
        return inf;
    }
}

ll safe_add(ll a, ll b) {
    if (a + b <= inf) {
        return a + b;
    } else {
        return inf;
    }
}

struct Kek {
    int a, b, k;
    bool is_big;
    ll ll_val;
    ld ld_val;
    Mint mint_val;
    Kek() {}
    Kek(int _a, int _b, int _k) : a(_a), b(_b), k(_k) {
        is_big = false;
        ll_val = 0;
        ld_val = logl(a) + k * logl(b) - logl(b - 1);
        mint_val = 0;
        for (int i = 0; i <= k - 1; i++) {
            ll_val = safe_mult(ll_val, b);
            ll_val = safe_add(ll_val, a);
            mint_val = mint_val * b + a;
        }
        is_big = ll_val == inf;
    }
    void increase() {
        k++;
        ld_val += logl(b);
        ll_val = safe_mult(ll_val, b);
        ll_val = safe_add(ll_val, a);
        mint_val = mint_val * b + a;
        is_big = ll_val == inf;
    }
    friend bool operator<(const Kek& l, const Kek& r) {
        if (l.is_big != r.is_big) {
            return l.is_big < r.is_big;
        } else if (!l.is_big) {
            return l.ll_val < r.ll_val;
        } else {
            return l.ld_val < r.ld_val;
        }
    }
    friend bool operator!=(const Kek& l, const Kek& r) {
        if (l.is_big != r.is_big) {
            return true;
        } else if (!l.is_big) {
            return l.ll_val != r.ll_val;
        } else {
            return abs(l.ld_val - r.ld_val) > eps;
        }
    }
};

const int N = 1e6 + 10;
const int M = 16 * 1e6 + 10;
Kek all[M];
Kek tmp[20];
Kek vals[N];
Mint pref[N];

void precalc() {
    const int trg_cnt = 1e6 + 100;
    int sz = 0;
    for (int b = 2; b <= 16; b++) {
        for (int a = 1; a <= b - 1; a++) {
            tmp[a] = Kek(a, b, 1);
            all[++sz] = tmp[a];
        }
        for (int i = 2; i <= trg_cnt / (b - 1); i++) {
            for (int a = 1; a <= b - 1; a++) {
                tmp[a].increase();
                all[++sz] = tmp[a];
            }
        }
    }
    sort(all + 1, all + sz + 1);
//    for (int i = 1; i <= 20; i++) {
//        cout << all[i].ll_val << " " << all[i].ld_val << " " << all[i].is_big << "\n";
//    }
    int n = 0;
    for (int i = 1; i <= sz && n + 1 < N; i++) {
        if (n == 0 || vals[n] != all[i]) {
            vals[++n] = all[i];
        }
    }
    // cout << n << "\n";
    for (int i = 1; i <= n; i++) {
        pref[i] = pref[i - 1] + vals[i].mint_val;
    }
//    for (int i = 1; i <= 40; i++) {
//        cout << vals[i].ll_val << "\n";
//    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
#endif

    precalc();

    int t;
    cin >> t;
    while (t--) {
        int l, r;
        cin >> l >> r;
        cout << pref[r] - pref[l - 1] << "\n";
    }

#ifdef LOCAL
    cout << "\nTime elapsed: " << double(clock()) / CLOCKS_PER_SEC << " s.\n";
#endif
}