F2. Appending Permutations (Hard Version)
time limit per test
3 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

This is the hard version of the problem. The difference between the versions is that in this version, $$$n \leq 5000$$$. You can hack only if you solved all versions of this problem.

You are given an initially empty array $$$a$$$. You may perform the following operation any number of times:

  • Choose an integer $$$s \ge 1$$$ and append a cyclic shift of the array $$$[1, 2, \ldots, s]$$$ to the end of $$$a$$$. Formally, select integers $$$s$$$ and $$$r$$$ such that $$$1 \le r \le s$$$, and append the array

    $$$$$$ [r, r+1, \ldots, s, 1, 2, \ldots, r-1] $$$$$$

    to the end of $$$a$$$.

You are also given an integer $$$n$$$ and $$$m$$$ restrictions of the form $$$a_i \ne x$$$. That is, for each of the $$$m$$$ restrictions, the value at position $$$i$$$ in the final array must not be equal to $$$x$$$.

Your task is to count the number of distinct arrays of length exactly $$$n$$$ that can be constructed using the allowed operation and satisfy all of the given restrictions. Two arrays are considered different if they differ at any position from $$$1$$$ to $$$n$$$.

Print the answer modulo $$$998\,244\,353$$$.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 5000$$$). The description of the test cases follows.

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \leq n \leq 5000, 0 \leq m \leq \min(5000, n^2)$$$) — the length of the array $$$a$$$ and the number of restrictions.

The following $$$m$$$ lines each contain two integers $$$i$$$ and $$$x$$$ ($$$1 \leq i,x \leq n$$$), indicating that $$$a_i\neq x$$$ is a requirement of the final array. It is guaranteed that no limitation is given more than once.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$5000$$$, and the sum of $$$m$$$ over all test cases does not exceed $$$5000$$$.

Output

For each test case, output the number of arrays modulo $$$998\,244\,353$$$.

Examples
Input
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
Output
7
0
1
65
0
4
5
Input
1
5000 1
69 420
Output
886908216
Note

In the first test case, there are $$$7$$$ total attainable arrays: $$$[1,2,3], [2,3,1], [3,1,2], [1,1,2], [1,2,1], [2,1,1], [1,1,1]$$$.

In the second test case, none of the above $$$7$$$ are valid because no element is allowed to be $$$1$$$, and all of the arrays have at least one $$$1$$$.

In the third case, only $$$[2,3,1]$$$ is counted.