#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N=4e3+10,mod=998244353;
const double eps=1e-7;

ll power(ll a,ll b){
    ll ans=1;
    for(;b;b>>=1){
        if(b&1)ans=ans*a%mod;
        a=a*a%mod;
    }
    return ans;
}

int n,m;
int L[N],R[N],b[N],top,cnt[N];
double d[N];
bool v[N];
vector<int> g[N];

bool SPFA(double val){
    queue<int> q;
    for(int i=1;i<=top;i++){
        d[i]=0,v[i]=1,cnt[i]=0;
        q.emplace(i);
    }
    while(q.size()){
        int x=q.front();
        q.pop();v[x]=0;
        cnt[x]++;
        if(cnt[x]>top)return 0;
        if(x<top){
            if(d[x+1]>d[x]){
                d[x+1]=d[x];
                if(!v[x+1])q.emplace(x+1),v[x+1]=1;
            }
        }
        for(auto y:g[x]){
            double z=(x<y?-1:val);
            if(d[y]>d[x]+z){
                d[y]=d[x]+z;
                if(!v[y])q.emplace(y),v[y]=1;
            }
        }
    }
    return 1;
}

void solve(){
    scanf("%d%d",&n,&m);
    top=0;
    for(int i=1;i<=m;i++){
        scanf("%d%d",&L[i],&R[i]);
        L[i]--;
        b[++top]=L[i],b[++top]=R[i];
    }
    sort(b+1,b+top+1),top=unique(b+1,b+top+1)-(b+1);
    for(int i=1;i<=top;i++)g[i].clear();
    for(int i=1;i<=m;i++){
        L[i]=lower_bound(b+1,b+top+1,L[i])-b;
        R[i]=lower_bound(b+1,b+top+1,R[i])-b;
        g[L[i]].emplace_back(R[i]),g[R[i]].emplace_back(L[i]);
    }
    double l=0,r=m*5;
    int T=50;
    while(T--){
        double mid=(l+r)/2;
        if(SPFA(mid))r=mid;
        else l=mid;
    }
    // printf("%lf %lf\n",l,r);

    for(int i=1;i<=m*5;i++){
        double val=l*i;
        ll now=(ll)val;
        while(now>val+0.5)now--;
        while(now<val-0.5)now++;
        if(abs(now-val)<eps){
            printf("%lld\n",now%mod*power(i,mod-2)%mod);
            return;
        }
    }
}

int main(){
    freopen("test.in","r",stdin);
    freopen("test.out","w",stdout);
    int T;scanf("%d",&T);
    while(T--)solve();
    return 0;
}