#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;}