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$$$.

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.

Appending Permutations (Hard Version)

Examples