#include <bits/stdc++.h>

using namespace std;
#define int long long
#define app push_back
#define all(x) (x).begin(),(x).end()
#ifdef LOCAL
#define debug(...) [](auto...a){ ((cout << a << ' '), ...) << endl;}(#__VA_ARGS__, ":", __VA_ARGS__)
#else
#define debug(...)
#endif
#ifdef LOCAL
#define __int128 long long
#endif // LOCAL
#define double long double
const int p=998244353;
int po(int a,int b) {if(b==0) return 1; if(b==1) return a; if(b%2==0) {int u=po(a,b/2);return (u*u)%p;} else {int u=po(a,b-1);return (a*u)%p;}}
int inv(int x) {return po(x,p-2);}
const int inf=1e18;
set<int> small;
int32_t main()
{
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    vector<pair<double,int> > v;
    for(int b=2;b<=16;++b)
    {
        debug(b);
        for(int i=1;i<b;++i)
        {
            if(b==4 && i==3) continue;
            if(b==9 && i==4) continue;
            if(b==9 && i==8) continue;
            if(b==8 && i==7) continue;
            if(b==16 && i==5) continue;
            if(b==16 && i==10) continue;
            if(b==16 && i==15) continue;
            double x=log(b);double y=log(b-1);double z=log(i);
            double cur=1;int cur1=1;
            int ib=inv(b-1);
            for(int len=1;len<40000;++len)
            {
                int ost=(((po(b,len)-1)*i)%p)*ib;ost%=p;
                if(ost==780136138) {debug(i,b,len);}
                double h=0;
                if(len>=40)
                {
                    h=z+len*x-y;
                }
                else
                {
                    cur*=b;cur1*=b;
                    h=z+log(cur-1)-y;
                    if(cur<1e17)
                    {
                        if(small.count(i*(cur1-1)/(b-1))) {continue;}
                        small.insert(i*(cur1-1)/(b-1));
                    }
                }
                v.app({h,ost});
            }
        }
    }
    sort(all(v));v.erase(unique(all(v)),v.end());
    //vector<pair<double,int> > v1;for(int i=0;i<v.size();++i) {if(i==0 || v[i].second!=v[i-1].second) {v1.app(v[i]);}}
    //v=v1;
    vector<int> pref(v.size()+1);pref[0]=0;for(int i=0;i<v.size();++i) {pref[i+1]=(pref[i]+v[i].second)%p;}
    int q;cin>>q;while(q--) {int l,r;cin>>l>>r;--l;cout<<((pref[r]-pref[l])%p+p)%p<<'\n';}
    return 0;
}