#include <bits/stdc++.h>
using namespace std;

#define rep(i, from, to) for (int i = from; i < (to); ++i)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
const int mod = 998244353;
int inv(int a) {
    return a < 2 ? a :
        mod - (mod / a) * 1ll * inv(mod % a) % mod;
}
bool chmin(ll &x, ll y) {
    if(x > y) {
        x = y;
        return true;
    }
    return false;
}
int main() {
    ios_base::sync_with_stdio(0);
    cout.tie(0);
    int T;
    cin >> T;
    while(T--) {
        int n, m;
        cin >> n >> m;
        vector<array<int, 2>> segs(m);
        for(auto &[l, r] : segs) cin >> l >> r, l--;

        vector<array<int, 2>> frac;
        for(int i = 1; i <= m; i++) {
            for(int j = 1; j <= m; j++) {
                frac.push_back({i, j});
            }
        }
        sort(all(frac), [&](auto x, auto y) {
            return x[0] * y[1] < y[0] * x[1];
        });
        auto check = [&](int id) -> bool {
            if(id >= frac.size()) return 0;
            ll high = frac[id][0], low = frac[id][1];
            /*
            p[l] <= p[r] - low
            p[r] <= p[l] + high
            p[l] <= p[l + 1]
            */
            vector<ll> dist(n + 1, 0);
            for(int iter = 0; iter <= n; iter++) {
                bool upd = false;
                for(int i = n + 1; i-- > 1;)
                    upd |= chmin(dist[i - 1], dist[i]);
                for(auto [l, r] : segs) {
                    upd |= chmin(dist[l], dist[r] - low);
                    upd |= chmin(dist[r], dist[l] + high);
                }
                if(iter == n && upd) {
                    // cout << high << " " << low << " false" << endl;
                    return false;
                }
            }
                    // cout << high << " " << low << " true" << endl;
            return 1;
        };
        int ans = -1;
        for(int z = 1<<25; z>>=1;) {
            ans += z*(ans + z < frac.size() && !check(ans+z));
        }
        ans++;
        // cout << frac[ans][0] << " " << frac[ans][1] << endl;
        cout << (frac[ans][0] * 1ll * inv(frac[ans][1])) % mod << '\n';
    }
}