Hyperregular Bracket Strings

Description:

Input:

Each test contains multiple test cases. The first line of input contains a single integer $$$t$$$ ($$$1 \le t \le 10^5$$$) — the number of test cases. The description of test cases follows.

The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 3 \cdot 10^5$$$, $$$0 \le k \le 3 \cdot 10^5$$$) — the length of the hyperregular bracket sequences and the number of intervals respectively.

The following $$$k$$$ lines of each test case contains two integers $$$l_i$$$ and $$$r_i$$$ ($$$1 \le l \le r \le n$$$).

It is guaranteed that the sum of $$$n$$$ across all test cases does not exceed $$$3 \cdot 10^5$$$ and the sum of $$$k$$$ across all test cases does not exceed $$$3 \cdot 10^5$$$.

Output:

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

Sample Input:

7
6 0
5 0
8 1
1 3
10 2
3 4
6 9
1000 3
100 701
200 801
300 901
28 5
1 12
3 20
11 14
4 9
18 19
4 3
1 4
1 4
1 4

Sample Output:

5
0
0
4
839415253
140
2

Note:

• For the first testcase, the $$$5$$$ hyperregular bracket strings of length $$$6$$$ are: ((())), (()()), (())(), ()(()) and ()()().
• For the second testcase, there are no regular bracket strings of length $$$5$$$, and consequently, there are no hyperregular bracket strings of length $$$5$$$.
• For the third testcase, there are no hyperregular bracket strings of length $$$8$$$ for which the substring $$$[1 \ldots 3]$$$ is a regular bracket string.
• For the fourth testcase, there $$$4$$$ hyperregular bracket strings are: ((())(())), ((())()()), ()()((())) and ()()(()())