#include <algorithm>
#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';
  }
}

answer.code: In function ‘int main()’:
answer.code:14:16: error: structured binding refers to incomplete type ‘std::array<int, 2>’
   14 |     for (auto& [l, r]: v) cin >> l >> r, pts.insert(pts.end(), {--l, r});
      |                ^~~~~~
answer.code:14:52: error: no matching function for call to ‘std::vector<int>::insert(std::vector<int>::iterator, <brace-enclosed initializer list>)’
   14 |     for (auto& [l, r]: v) cin >> l >> r, pts.insert(pts.end(), {--l, r});
      |                                          ~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/13/vector:66,
                 from answer.code:4:
/usr/include/c++/13/bits/stl_vector.h:1479:9: note: candidate: ‘template<class _InputIterator, class> constexpr std::vector<_Tp, _Alloc>::iterator std::vector<_Tp, _Alloc>::insert(const_iterator, _InputIterator, _InputIterator) [with <template-parameter-2-2> = _InputIterator; _Tp = int; _Alloc = std::allocator<int>]’
 1479 |         insert(const_iterator __position, _InputIterator __first,
      |         ^~~~~~
/usr/include/c++/13/bits/stl_vector.h:1479:9: note:   template argument deduction/substitution failed:
answer.code:14:52: note:   candidate expects 3 arguments, 2 provided
   14 |     for (auto& [l, r]: v) cin >> l >> r, pts.insert(pts.end(), {--l, r});
      |                                          ~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/13/vector:72:
/usr/include/c++/13/bits/vector.tcc:133:5: note: candidate: ‘constexpr std::vector<_Tp, _Alloc>::iterator std::vector<_Tp, _Alloc>::insert(const_iterator, const value_type&) [with _Tp = int; _Alloc = std::allocator<int>; iterator = std::vector<int>::iterator; const_iterator = std::vector<int>::const_iterator; value_type = int]’
  133 |     vector<_Tp, _Alloc>::
      |     ^~~~~~~~~~~~~~~~~~~
/usr/include/c++/13/bits/vector.tcc:135:57: note:   no known conversion for argument 2 from ‘<brace-enclosed initializer list>’ to ‘const std::vector<int>::value_type&’ {aka ‘const int&’}
  135 |     insert(const_iterator __position, const value_type& __x)
      |                                       ~~~~~~~~~~~~~~~~~~^~~
/usr/include/c++/13/bits/stl_vector.h:1390:7: note: candidate: ‘constexpr std::vector<_Tp, _Alloc>::iterator std::vector<_Tp, _Alloc>::insert(const_iterator, value_type&&) [with _Tp = int; _Alloc = std::allocator<int>; iterator = std::vector<int>::iterator; const_iterator = std::vector<int>::const_iterator; value_type = int]’
 1390 |       insert(const_iterator __position, value_type&& __x)
      |       ^~~~~~
/usr/include/c++/13/bits/stl_vector.h:1390:54: note:   no known conversion for argument 2 from ‘<brace-enclosed initializer list>’ to ‘std::vector<int>::value_type&&’ {aka ‘int&&’}
 1390 |       insert(const_iterator __position, value_type&& __x)
      |                                         ~~~~~~~~~~~~~^~~
/usr/include/c++/13/bits/stl_vector.h:1408:7: note: candidate: ‘constexpr std::vector<_Tp, _Alloc>::iterator std::vector<_Tp, _Alloc>::insert(const_iterator, std::initializer_list<_Tp>) [with _Tp = int; _Alloc = std::allocator<int>; iterator = std::vector<int>::iterator; const_iterator = std::vector<int>::const_iterator]’
 1408 |       insert(const_iterator __position, initializer_list<value_type> __l)
      |       ^~~~~~
/usr/include/c++/13/bits/stl_vector.h:1408:70: note:   no known conversion for argument 2 from ‘<brace-enclosed initializer list>’ to ‘std::initializer_list<int>’
 1408 |       insert(const_iterator __position, initializer_list<value_type> __l)
      |                                         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
/usr/include/c++/13/bits/stl_vector.h:1434:7: note: candidate: ‘constexpr std::vector<_Tp, _Alloc>::iterator std::vector<_Tp, _Alloc>::insert(const_iterator, size_type, const value_type&) [with _Tp = int; _Alloc = std::allocator<int>; iterator = std::vector<int>::iterator; const_iterator = std::vector<int>::const_iterator; size_type = long unsigned int; value_type = int]’
 1434 |       insert(const_iterator __position, size_type __n, const value_type& __x)
      |       ^~~~~~
/usr/include/c++/13/bits/stl_vector.h:1434:7: note:   candidate expects 3 arguments, 2 provided
answer.code:17:36: error: range-based ‘for’ expression of type ‘std::array<int, 2>’ has incomplete type
   17 |     for (auto& v: v) for (auto& v: v) v = lower_bound(pts.begin(), pts.end(), v) - pts.begin();
      |                                    ^
answer.code: In lambda function:
answer.code:24:19: error: deduced type ‘std::array<int, 2>’ for ‘<structured bindings>’ is incomplete
   24 |         for (auto [l, r]: v) {
      |                   ^~~~~~
In file included from /usr/include/c++/13/bits/uses_allocator_args.h:38,
                 from /usr/include/c++/13/bits/memory_resource.h:41,
                 from /usr/include/c++/13/string:58,
                 from /usr/include/c++/13/bits/locale_classes.h:40,
                 from /usr/include/c++/13/bits/io...