#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> mi, ma;
    auto check = [&](int w0, int w1) {
      mi.assign(pts.size() + 1, 0);
      ma.assign(pts.size() + 1, 1 << 30);
      ma[0] = 0;
      for (int _ = mi.size(); _--; ) {
        for (auto [l, r]: v) {
          mi[r] = max(mi[r], mi[l] + w0);
          ma[r] = min(ma[r], ma[l] + w1);
          mi[l] = max(mi[l], mi[r] - w1);
          ma[l] = min(ma[l], ma[r] - w0);
        }
        for (int i = 1; i < mi.size(); ++i) mi[i] = max(mi[i], mi[i - 1]);
        for (int i = mi.size() - 1; i--; ) ma[i] = min(ma[i], ma[i + 1]);
        for (int i = mi.size(); i--; ) if (mi[i] > ma[i]) return 0;
      }
      return 1;
    };
    int l = 0, r = n;
    while (r > l + 1) {
      int m = (l + r) / 2;
      (check(1, m)? r: l) = m;
    }
    vector<array<int, 2>> u;
    if (l == 0) u = {{1, 1}};
    else
    for (int q = 1; q <= n; ++q)
    for (int p = 0; p <= n; ++p) if (p <= r * q && p > l * q && 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]; });
    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';
  }
}