#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
using ll=long long;
using ld=long double;
using pii=pair<int,int>;
using vi=vector<int>;
using vl=vector<ll>;
#define pb push_back
#define all(a) begin(a),end(a)

const int N=1000010,MOD=998244353;
const char en='\n';
const ll LLINF=1ll<<60;

int add1(int a,int k,int j)
{
	return (a*1ll*k+j)%MOD;
}

pair<int,ld> add2(pair<int,ld> a,int k,int j)
{
	a.y*=k;
	a.y+=j*pow(1.L/16,a.x);
	while (a.y>=16)
	{
		++a.x;
		a.y/=16;
	}
	return a;
}

int t;
pair<int,ld> va[30][30];
int rva[30][30];
bool allo[30][30];
vi val;
vl pref;

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	const int B=16;
	for (int i=2;i<=B;++i) for (int j=1;j<i;++j) va[i][j]={0,j},rva[i][j]=j,allo[i][j]=1;
	allo[9][4]=0;
	allo[9][8]=0;
	allo[4][3]=0;
	allo[8][7]=0;
	allo[16][5]=0;
	allo[16][10]=0;
	allo[16][15]=0;
	while (val.size()<N)
	{
		//cout<<val.size()<<endl;
		pair<int,ld> mi=va[2][1];
		int rvaa=rva[2][1];
		pii kak={2,1};
		for (int i=2;i<=B;++i) for (int j=1;j<i;++j) if (allo[i][j] && va[i][j]<mi)
		{
			mi=va[i][j];
			rvaa=rva[i][j];
			kak={i,j};
		}
		for (int i=2;i<=B;++i) for (int j=1;j<i;++j) if (allo[i][j])
		{
			if ((va[i][j]==mi)!=(rva[i][j]==rvaa))
			{
				cout<<i<<' '<<j<<en<<va[i][j].x<<' '<<va[i][j].y<<' '<<rva[i][j]<<en;
				cout<<kak.x<<' '<<kak.y<<en<<mi.x<<' '<<mi.y<<' '<<rvaa<<en;
				exit(0);
			}
			if (va[i][j]==mi)
			{
				//cout<<i<<' '<<j<<' '<<mi.x<<' '<<mi.y<<' '<<rvaa<<' '<<rva[i][j]<<endl;
				va[i][j]=add2(va[i][j],i,j);
				rva[i][j]=add1(rva[i][j],i,j);
			}
		}
		val.pb(rvaa);
		//if (val.size()<20) cout<<"V"<<val.back()<<endl;
	}
	//cout<<en;
	pref.pb(0);
	for (auto x: val) pref.pb(pref.back()+x);
	cin>>t;
	while (t--)
	{
		int l,r;
		cin>>l>>r;
		--l;
		cout<<(pref[r]-pref[l])%MOD<<en;
	}
}