#include<bits/stdc++.h>
using namespace std;
constexpr int M=6005,mod=998244353;
int n,m,l[M],r[M],mn[M][M],mx[M][M];
struct info{int p,q;
    bool operator <(const info &a) const
        {return 1ll*p*a.q<1ll*a.p*q;}
}ans;
int tot,a[M];
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;
}
int test,TT;
pair<int,int>b[100100];
vector<int>g[100100];
int f[100100];
void solve(){
    test++;
    cin>>n>>m;ans={1,1};tot=0;
    for (int i=1;i<=m;i++) {
        cin>>l[i]>>r[i],a[++tot]=l[i],a[++tot]=r[i],a[++tot]=r[i]-1;
    }
    sort(a+1,a+tot+1);
    tot=unique(a+1,a+tot+1)-a-1;
    for (int i=1;i<=tot;i++)
    g[i].clear();
    for (int i=1;i<=m;i++)
    l[i]=lower_bound(a+1,a+tot+1,l[i])-a,
    r[i]=lower_bound(a+1,a+tot+1,r[i])-a,
    g[r[i]].push_back(l[i]);
    n=tot;
    // cout<<tot<<"******\n";
    for (int i=0;i<=n+1;i++)
        for (int j=0;j<=n+1;j++)
            mn[i][j]=0x3f3f3f3f,mx[i][j]=0;
    for (int i=1;i<=m;i++) 
        mx[l[i]][r[i]]=mn[l[i]][r[i]]=1;
    for (int len=n-1;len;len--){
        for (int l=1;l+len-1<=n;l++){
            int r=l+len-1;
            mn[l][r]=min(mn[l][r],min(mn[l][r+1],mn[l-1][r]));
        }
    }
    for (int l=n;l;l--){
        int st=0;
        for (int r=l;r<=n;r++){
            mx[l][r]=mx[l][r-1];
            for (auto k:g[r])if(k>=l){
                mx[l][r]=max(mx[l][r],max(mx[l][k-1],mx[l][k-1])+1);
                if(a[k-1]+1==a[k])mn[l][r]=min(mn[l][r],mn[l][k-1]+1);
                else {
                    int tmp=lower_bound(b+1,b+st+1,make_pair(k,0))-b;
                    // cout<<l<<"***"<<r<<" "<<k<<" "<<b[tmp].first<<"\n";
                    if(tmp<=st&&tmp>=1)mn[l][r]=min(mn[l][r],b[tmp].second+1);
                }
            }
            while(st&&mn[l][r]<=b[st].second)st--;
            b[++st]=make_pair(r,mn[l][r]);
        }
        for (int r=n-1;r>=l;r--)mn[l][r]=min(mn[l][r+1],mn[l][r]);
    }
    for (int i=1;i<=n;i++)
        for (int j=i;j<=n;j++){
        // cout<<i<<" "<<j<<" "<<mx[i][j]<<" "<<mn[i][j]<<"\n";
            if (mx[i][j])
            ans=max(ans,{mx[i][j],mn[i][j]});
        }
    if(ans.p==1&&ans.q==1){
        f[0]=1;
        for (int i=1;i<=n+1;i++){
            int rs=i-1,ls=0;f[i]=0;
            for (int j=1;j<=m;j++)
            if(r[j]>=i)rs=min(rs,l[j]-1);
            for (int j=i-1;j>=ls;j--){
                for (auto k:g[j])ls=max(ls,k);
                if(rs>=j)f[i]|=f[j];
            }
        }
        if(f[n+1]==0)ans={3,2};
    }
    cout<<1ll*ans.p*qpow(ans.q,mod-2)%mod<<'\n';
}
int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int T;cin>>T;TT=T;
    while (T--) solve();return 0;
}