F1. Appending Permutations (Easy Version)time limit per test3 secondsmemory limit per test1024 megabytesinputstandard inputoutputstandard output This is the easy version of the problem. The difference between the versions is that in this version, $$$n \leq 100$$$. 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$$$.InputEach test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 100$$$). The description of the test cases follows. The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \leq n \leq 100, 0 \leq m \leq \min(5000, n^2)$$$) — denoting 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 $$$100$$$, and the sum of $$$m$$$ over all test cases does not exceed $$$5000$$$. OutputFor each test case, output the number of arrays modulo $$$998\,244\,353$$$.ExamplesInput73 03 31 12 13 13 21 12 16 22 34 22 31 22 21 14 32 23 24 23 22 33 3Output7 0 1 65 0 4 5 Input1100 169 69Output381055417 NoteIn 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.