#include<bits/stdc++.h>
using namespace std;
constexpr int N=4005,M=2005,mod=998244353;
bool vis[N];int cnt[N],lsh[N];long long dis[N];
int n,m,l[M],r[M],Gcd[M][M];
struct frac{ int x,y;
    bool operator <(const frac &a) const
        {return x*a.y<a.x*y;}
};
int read(){
	int x=0;char ch=getchar();
	while (!isdigit(ch)) ch=getchar();
	while (isdigit(ch)) x=x*10+ch-48,ch=getchar();
	return x;
}
int qpow(int x,int n){
	int s=1; while (n){
		if (n&1) s=1ll*s*x%mod;
		x=1ll*x*x%mod; n>>=1;
	} return s;
}
bool chkmin(long long &a,long long b){return a>b?a=b,1:0;}
bool check(int a,int b){
    for (int i=0;i<=n;i++) dis[i]=0;
    for (int k=1;k<=n;k++){
        bool flag=0;
        for (int i=1;i<=m;i++)
            flag|=chkmin(dis[l[i]],dis[r[i]]-b),
            flag|=chkmin(dis[r[i]],dis[l[i]]+a);
        for (int i=1;i<=n;i++) flag|=chkmin(dis[i-1],dis[i]);
        if (!flag) return 1;
        if (dis[n]<0) return 0;
    }
    return 0;
}
void solve(){
	n=0;read();m=read();
	for (int i=1;i<=m;i++)
		lsh[++n]=l[i]=read()-1,lsh[++n]=r[i]=read();
	sort(lsh+1,lsh+n+1);n=unique(lsh+1,lsh+n+1)-lsh-1;
	for (int i=1;i<=m;i++)
		l[i]=lower_bound(lsh+1,lsh+n+1,l[i])-lsh,
		r[i]=lower_bound(lsh+1,lsh+n+1,r[i])-lsh;
	for (int i=1;i<=m;i++)
		for (int j=1;j<=m;j++)
			Gcd[i][j]=0;
	vector<frac>Ans;
	for (int d=m;d;d--)
		for (int i=d;i<=m;i+=d)
			for (int j=d;j<=m;j+=d)
				if (!Gcd[i][j]) Gcd[i][j]=d;
	for (int i=1;i<=m;i++)
		for (int j=1;j<=i;j++)
			if (Gcd[i][j]==1&&i+j<=m)
				Ans.push_back({i,j});
	sort(Ans.begin(),Ans.end());
	int l=0,r=(int)Ans.size()-1,ans;
	while (l<=r){
		int mid=l+r>>1;
		if (check(Ans[mid].x,Ans[mid].y))
			ans=mid,r=mid-1;
		else l=mid+1;
	}
	printf("%lld\n",1ll*Ans[ans].x*qpow(Ans[ans].y,mod-2)%mod);
}
int main(){int T=read();while (T--) solve();return 0;}