#include <algorithm>
#include <array>
#include <cstdint>
#include <iostream>
#include <numeric>
#include <vector>

using namespace std;

int main() {
  cin.tie(0)->sync_with_stdio(0);
  for (int tc = (cin >> tc, tc); tc--; ) {
    int n; cin >> n >> n;
    vector<int> pts;
    vector<array<int, 2>> v(n);
    for (auto& [l, r]: v) cin >> l >> r, pts.insert(pts.end(), {--l, r});
    sort(pts.begin(), pts.end());
    pts.erase(unique(pts.begin(), pts.end()), pts.end());
    for (auto& v: v) for (auto& v: v) v = lower_bound(pts.begin(), pts.end(), v) - pts.begin();
    vector<int> ps;
    auto check = [&](int w0, int w1) {
      ps.assign(pts.size() + 1, 0);
      for (int _ = ps.size(); _--; ) {
        for (int i = 1; i < ps.size(); ++i) if (ps[i] = max(ps[i], ps[i - 1]), ps[i] > 1e9) return 0;
        for (auto [l, r]: v) ps[r] = max(ps[r], ps[l] + w0), ps[l] = max(ps[l], ps[r] - w1);
      }
      return +is_sorted(ps.begin(), ps.end());
    };
    vector<array<int, 2>> u;
    for (int q = 1; q <= n; ++q)
    for (int p = q; p <= n; ++p) if (gcd(p, q) == 1) u.push_back({p, q});
    sort(u.begin(), u.end(), [](auto& a, auto& b) { return a[0] * b[1] < a[1] * b[0]; });
    int l = -1, r = u.size() - 1;
    while (r > l + 1) {
      int m = (l + r) / 2;
      (check(u[m][1], u[m][0])? r: l) = m;
    }
    int64_t p = u[r][0], q = u[r][1];
    while (p % q) p += 998244353;
    cout << p / q << '\n';
  }
}