#include<bits/stdc++.h>
using namespace std;
int main()
{
	ios_base::sync_with_stdio(false);
	int T;
	cin>>T;
	while(T--)
	{
		int n,m;
		cin>>n>>m;
		vector<int> L(m+5),R(m+5);
		map<int,int> mp;
		for(int i=1;i<=m;i++)
		{
			cin>>L[i]>>R[i];
			mp[L[i]]=mp[R[i]+1]=0;
		}
		int idx=0;
		for(auto &[x,y]:mp)
		{
			y=++idx;
		}
		for(int i=1;i<=m;i++)
		{
			L[i]=mp[L[i]];
			R[i]=mp[R[i]+1];
		}
		//[li,ri)
		auto check=[&](int P,int Q)
		{
			vector<vector<pair<int,int>>> G(idx+5);
			for(int i=1;i<=m;i++)
			{
				G[L[i]].emplace_back(R[i],P);
				G[R[i]].emplace_back(L[i],-Q);
			}
			for(int i=1;i<idx;i++)
				G[i+1].emplace_back(i,0);
			vector<long long> dis(idx+5),cnt(idx+5);
			queue<int> q;
			for(int i=1;i<=idx;i++)
			{
				q.push(i);
			}
			while(not q.empty())
			{
				int u=q.front();q.pop();
				for(auto [v,w]:G[u])
				{
					if(dis[v]>dis[u]+w)
					{
						dis[v]=dis[u]+w;
						cnt[v]++;
						if(cnt[v]>idx)return false;
						q.push(v);
					}
				}
			}
			return true;
		};
		/*
		for(int i=1;i<=5;i++)
			for(int j=1;j<=i;j++)
			{
				if(gcd(i,j)!=1)continue;
				cerr<<i<<' '<<j<<' '<<check(i,j)<<endl;
			}
		*/
		const int lim=1e9;//4000*4000;
		struct frac
		{
			int p,q;
			frac operator+(const frac &f)const{return {p+f.p,q+f.q};}
			frac operator*(const int k)const{return {p*k,q*k};}
			bool operator<(const frac &f)const{return 1ll*p*f.q<1ll*q*f.p;}
		}ans{lim,1},l{1,1},r{1,0};
		if(check(1,1))
		{
			ans={1,1};
		}
		int dir=0;
		while(1)
		{
//			cerr<<"gp "<<l.p<<"/"<<l.q<<'~'<<r.p<<"/"<<r.q<<endl;
			if((l+r).p>lim or (l+r).q>lim)break;
			if(dir==0)
			{
				int kl=1,kr=min((lim-r.p)/l.p,(lim-r.q)/l.q);
				while(kl<kr)
				{
					int km=(kl+kr+1)/2;
					frac tmp=l*km+r;
					if(check(tmp.p,tmp.q))
					{
						if(tmp<ans)ans=tmp;
						kl=km;
					}
					else
						kr=km-1;
				}
				r=l*kl+r;
				if(r<ans and check(r.p,r.q))ans=r;
				dir^=1;
			}
			else
			{
				int kl=1,kr=min((lim-l.p)/r.p,(lim-l.q)/r.q);
				while(kl<kr)
				{
					int km=(kl+kr)/2;
					frac tmp=l+r*km;
					if(check(tmp.p,tmp.q))
					{
						if(tmp<ans)ans=tmp;
						kr=km;
					}
					else
						kl=km+1;
				}
				l=l+r*kl;
				if(l<ans and check(l.p,l.q))ans=l;
				dir^=1;
			}
		}
		const int MOD=998244353;
		auto poww=[&](long long x,int y)
		{
			long long ret=1;
			while(y)
			{
				if(y&1)ret*=x,ret%=MOD;
				x*=x,x%=MOD;
				y>>=1;
			}
			return ret;
		};
//		cerr<<"ans = "<<ans.p<<'/'<<ans.q<<endl;
		cout<<1ll*ans.p*poww(ans.q,MOD-2)%MOD<<"\n";
	}
	
	return 0;
}