F2. 追加排列（困难版）
时间限制：3 秒
内存限制：1024 兆字节

这是问题的困难版本。与简单版本的区别在于，本版本中 $n \le 5000$。只有解决了所有版本的问题，你才能进行 hack。

你有一个初始为空的数组 $a$。你可以执行以下操作任意次：

• 选择一个整数 $s \ge 1$，并将数组 $[1,2,\dots,s]$ 的某个循环移位追加到 $a$ 的末尾。形式化地说，选择整数 $s$ 和 $r$（$1 \le r \le s$），并将数组$$[r, r+1, \dots, s, 1, 2, \dots, r-1]$$ 追加到 $a$ 的末尾。

你还得到一个整数 $n$ 以及 $m$ 条限制，形如 $a_i \neq x$。也就是说，对于每条限制，最终数组的第 $i$ 个位置上的值不能等于 $x$。

你的任务是统计：通过允许的操作，可以构造出的长度为 $n$ 的、满足所有限制的不同数组的个数。如果两个数组在某个位置 $1$ 到 $n$ 上不同，则认为它们不同。

输出答案对 $998244353$ 取模。

输入
每个测试包含多个测试用例。第一行包含测试用例数 $t$（$1 \le t \le 5000$）。

每个测试用例的第一行包含两个整数 $n$ 和 $m$（$1 \le n \le 5000$，$0 \le m \le \min(5000, n^2)$）—— 数组 $a$ 的长度和限制的数量。

接下来的 $m$ 行，每行包含两个整数 $i$ 和 $x$（$1 \le i, x \le n$），表示要求 $a_i \neq x$。保证不会重复给出同一条限制。

保证所有测试用例的 $n$ 之和不超过 $5000$，$m$ 之和不超过 $5000$。

输出
对于每个测试用例，输出满足条件的数组个数，对 $998244353$ 取模。

样例
输入

7
3 0
3 3
1 1
2 1
3 1
3 2
1 1
2 1
6 2
2 3
4 2
2 3
1 2
2 2
1 1
4 3
2 2
3 2
4 2
3 2
2 3
3 3

输出

7
0
1
65
0
4
5

输入

1
5000 1
69 420

输出

886908216

说明

• 第一个测试用例中，总共可以构造出 $7$ 个数组：
  $[1,2,3], [2,3,1], [3,1,2], [1,1,2], [1,2,1], [2,1,1], [1,1,1]$。
• 第二个测试用例中，上述 $7$ 个数组都不满足限制（因为所有数组都至少包含一个 $1$），因此答案为 $0$。
• 第三个测试用例中，只有 $[2,3,1]$ 符合要求。