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

const int md = 998244353;
#define double long double

inline int mul(int x, int y) {
    return 1ull * x * y % md;
}

inline int fpow(int x, int y) {
    int ans = 1;
    while (y) {
        if (y & 1) ans = mul(ans, x);
        y >>= 1; x = mul(x, x);
    }
    return ans;
}

const int N = 4005;

int l[N], r[N], b[N];
int T, n, m, ans1, ans2;

namespace dcx {

const int N = 4005, M = 4005;
const double eps = 1e-14;

double a[N][M];
int n, m;

#define L(i, j, k) for(int i = (j); i <= (k); ++i)

void pivot(int u, int v) {
    if(fabs(a[u][v]) <= eps) while (true);
    double iv = 1. / a[u][v];
    L(i, 0, n) a[u][i] *= iv;
    a[u][v] = iv; 
    L(i, 0, m) if(i != u && fabs(a[i][v]) > 0) {
        double c = a[i][v];
        a[i][v] = 0;
        L(j, 0, n) a[i][j] -= a[u][j] * c;
    }
}
double simplex() {
    a[0][0] = 0;
    while (true) {
        int u = 1, v = -1;
        L(i, 1, m) if(a[i][0] < a[u][0]) u = i;
        if(a[u][0] >= -eps) break ; 
        L(i, 1, n) if(a[u][i] < -eps) v = i;
        if(v == -1) {
            assert(0);
        }
        pivot(u, v);
    } 
    while (true) {
        int u = -1, v = 1;
        L(i, 1, n) if(a[0][i] < a[0][v]) v = i;
        if(a[0][v] >= -eps) break ; 
        double mn = 1e18;
        L(i, 1, m) if(a[i][v] > eps) {
            double qwq = a[i][0] / a[i][v];
            if(qwq < mn) u = i, mn = qwq;
        }
        if(u == -1) {
            assert(0);
        }
        pivot(u, v);
    }
    return a[0][0];
}

}

int main() {
    scanf("%d", &T);
    while (T--) {
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= m; i++) {
            scanf("%d%d", &l[i], &r[i]);
            b[i] = l[i]; b[i + m] = r[i];
        }
        sort(b + 1, b + 2 * m + 1);
        int len = unique(b + 1, b + 2 * m + 1) - b - 1;
        dcx::m = m * 2;
        dcx::n = len + 1;
        for (int i = 1; i <= len; i++) dcx::a[0][i] = 0;
        dcx::a[0][len + 1] = 1;
        for (int i = 1; i <= m; i++) {
            l[i] = lower_bound(b + 1, b + len + 1, l[i]) - b;
            r[i] = lower_bound(b + 1, b + len + 1, r[i]) - b;
            memset(dcx::a[i * 2 - 1], 0, sizeof(dcx::a[i * 2 - 1]));
            memset(dcx::a[i * 2], 0, sizeof(dcx::a[i * 2 - 1]));
            for (int j = l[i]; j <= r[i]; j++) {
                dcx::a[i * 2 - 1][j] = -1;
                dcx::a[i * 2][j] = 1;
            }
            dcx::a[i * 2 - 1][0] = -1;
            dcx::a[i * 2][len + 1] = -1;
        }
        double res = -dcx::simplex();
        // fprintf(stderr, "res = %.6lf\n", res);
        double mn = 1e9;
        int ans = 0;
        for (int i = 1; ; i++) {
            ll j = floor(1ll * i * res + 0.5);
            double diff = fabs((double)j / i - res);
            // fprintf(stderr, "i = %d, j = %d\n", i, j);
            if (diff < mn) {
                mn = diff;
                ans = mul(j % md, fpow(i, md - 2));
                if (diff < 1e-12) {
                    break;
                }
                // fprintf(stderr, "ans = %d, i = %d, j = %d, diff = %.6lf\n", ans, i, j, diff);
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}

/*
3
3 3
1 3
2 3
1 2
12 6
2 3
5 7
1 9
4 8
1 2
7 11
4 5
3 4
2 3
1 2
4 4
1 1
*/

answer.code: In function ‘int main()’:
answer.code:108:13: error: ‘ll’ was not declared in this scope; did you mean ‘l’?
  108 |             ll j = floor(1ll * i * res + 0.5);
      |             ^~
      |             l
answer.code:109:40: error: ‘j’ was not declared in this scope
  109 |             double diff = fabs((double)j / i - res);
      |                                        ^
answer.code:78:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   78 |     scanf("%d", &T);
      |     ~~~~~^~~~~~~~~~
answer.code:80:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   80 |         scanf("%d%d", &n, &m);
      |         ~~~~~^~~~~~~~~~~~~~~~
answer.code:82:18: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   82 |             scanf("%d%d", &l[i], &r[i]);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~~