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

const int MXM = 4005;
const int DVS = 998244353;
const int MXL = MXM * MXM;
int T, M, bnd[MXM], xx[MXM], xs;
int slen;
pair<int, int> fs[MXL];

void generate(int a, int b, int c, int d) {
  if (b + d > M) return;
  generate(a, b, a + c, b + d);
  fs[slen++] = make_pair(a + c, b + d);
  generate(a + c, b + d, c, d);
}

bool check(int id) {
  static long long dis[MXM];
  static long long INF = 1e18;
  int lb(fs[id].first), rb(fs[id].second);
  for (int i(1); i != xs; ++i) dis[i] = INF;
  dis[0] = 0;
  for (int i(0); i <= xs; ++i) {
    bool run(false);
    for (int j(0); j != xs - 1; ++j)
      if (dis[j] > dis[j + 1]) dis[j] = dis[j + 1], run = true;
    for (int j(0); j != M; j += 2) {
      int l(bnd[j]), r(bnd[j + 1]);
      if (dis[l] > dis[r] - lb) dis[l] = dis[r] - lb, run = true;
      if (dis[r] > dis[l] + rb) dis[r] = dis[l] + rb, run = true;
    }
    if (!run) return true;
  }
  return false;
}

void exgcd(int a, int b, int& x, int& y) {
  if (!b) x = 1, y = 0;
  else exgcd(b, a % b, y, x), y -= a / b * x;
}
inline int getinv(int a) {
  int x(0), y(0);
  exgcd(a, DVS, x, y);
  return (x % DVS + DVS) % DVS;
}

int main() {
  cin >> T;
  while (T--) {
    cin >> M >> M, M *= 2;
    for (int i(0); i != M; ++i) {
      cin >> bnd[i];
      if (i % 2 == 0) --bnd[i];
    }
    copy(bnd, bnd + M, xx);
    sort(xx, xx + M);
    xs = unique(xx, xx + M) - xx;
    for (int i(0); i != M; ++i) bnd[i] = lower_bound(xx, xx + xs, bnd[i]) - xx;
    generate(0, 1, 1, 1);
    fs[slen++] = make_pair(1, 1);
    int L(0), R(slen);
    while (R - L > 1) {
      int mid((L + R) >> 1);
      if (check(mid)) L = mid;
      else R = mid;
    }
    cout << fs[L].second * 1LL * getinv(fs[L].first) % DVS << endl;
  }
  return 0;
}