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). () r, r+1, \ldots, s, 1, 2, \ldots, r-1 () to the end of (a). 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). 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). For each test case, output the number of arrays modulo (998\,244\,353). 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) a