#include<bits/stdc++.h>
// #pragma GCC optimize("trapv")
#define int long long
#define double long double
using namespace std;

const int N=8007;
const int mod=998244353;
const double EPS=1e-9;
int n,m;
int l[N],r[N];
vector<pair<int,double>> g[N];
double dist[N];
int check(double x){
    // cerr<<x<<endl;
    for (int i=0;i<=2*m;++i) dist[i]=0, g[i].clear();
    for (int i=0;i<2*m;++i) g[i+1].push_back({i,0}); 
    for (int i=0;i<m;++i){
        // cerr<<l[i]<<" "<<r[i]<<endl;
        g[l[i]].push_back({r[i],x});
        g[r[i]].push_back({l[i],-1});
    }
    for (int i=0;i<=2*m;++i){
        bool ok=1;
        for (int u=0;u<=2*m;++u){
            for (auto [v,d]:g[u]) {
                if (dist[v]>dist[u]+d+EPS) dist[v]=dist[u]+d, ok=0;
            }
        }
        if (ok) return 1;
    }
    return 0;
}

int modpow(int u,int v){
    int ans=1, t=u;
    while (v){
        if (v&1) ans=ans*t%mod;
        t=t*t%mod, v>>=1;
    }
    return ans;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int _;
    cin>>_;
    while (_--){
        cin>>n>>m;
        vector<int> lst;
        for (int i=0;i<m;++i) cin>>l[i]>>r[i], l[i]--, lst.push_back(l[i]), lst.push_back(r[i]);
        sort(lst.begin(), lst.end());
        for (int i=0;i<m;++i) l[i]=lower_bound(lst.begin(), lst.end(),l[i])-lst.begin(), r[i]=lower_bound(lst.begin(), lst.end(), r[i])-lst.begin();
        double L=1.0, R=2000.0;
        while (R-L>EPS){
            double md=(L+R)/2;
            if (check(md)) R=md;
            else L=md;
        }
        // cout<<L<<"\n";
        int idx=-1, v=-1;
        for (int i=1;i<=m*m;++i){
            int x=i*L+0.001;
            // cerr<<i*L-x<<endl;
            if (abs(i*L-x)<100*EPS) {idx=i, v=x; break;}
        }
        assert(idx!=-1);
        cout<<v*modpow(idx,mod-2)%mod<<"\n";
    }
}