#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-12;

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

void pivot(int r, int c) {
    double tmp = -a[r][c]; a[r][c] = -1;
    for (int i = 0; i <= n; i++) a[r][i] /= tmp;
    for (int i = 0; i <= m; i++) {
        if (i != r && fabs(a[i][c]) > eps) {
            tmp = a[i][c]; a[i][c] = 0;
            for (int j = 0; j <= n; j++) a[i][j] += tmp * a[r][j];
        }
    }
}

double simplex() {
    a[0][0] = 0;
    while (1) {
        int r = -1;
        for (int i = 1; i <= m; i++) {
            if (a[i][0] < -eps) {
                if (r == -1 || a[i][0] < a[r][0]) {
                    r = i;
                }
            }
        }
        if (r == -1) break;
        int c = -1;
        for (int i = 1; i <= n; i++)  {
            if (a[r][i] > eps) {
                c = i;
                break;
            }
        }
        assert(c != -1);
        pivot(r, c);
    }
    while (1) {
        int c = -1;
        for (int i = 1; i <= n; i++) {
            if (a[0][i] > eps) {
                c = i;
                break;
            }
        }
        if (c == -1) break;
        int r = -1; double lim;
        for (int i = 1; i <= m; i++) {
            if (a[i][c] < -eps) {
                double now = a[i][0] / -a[i][c];
                if (r == -1 || now < lim) {
                    lim = now;
                    r = i;
                }
            }
        }
        assert(r != -1);
        pivot(r, c);
    }
    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 <= m; i++) {
            int j = floor(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, fpow(i, md - 2));
                // 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
*/