Nested Segments
Description
A set $A$ consisting of pairwise distinct segments $[l, r]$ with integer endpoints is called good if $1\le l\le r\le n$, and for any pair of distinct segments $[l_i, r_i], [l_j, r_j]$ in $A$, exactly one of the following conditions holds:
- $r_i < l_j$ or $r_j < l_i$ (the segments do not intersect)
- $l_i \le l_j \le r_j \le r_i$ or $l_j \le l_i \le r_i \le r_j$ (one segment is fully contained within the other)
You are given a good set $S$ consisting of $m$ pairwise distinct segments $[l_i, r_i]$ with integer endpoints. You want to add as many additional segments to the set $S$ as possible while ensuring that set $S$ remains good.
Since this task is too easy, you need to determine the number of different ways to add the maximum number of additional segments to $S$, ensuring that the set remains good. Two ways are considered different if there exists a segment that is being added in one of the ways, but not in the other.
Formally, you need to find the number of good sets $T$ of distinct segments, such that $S$ is a subset of $T$ and $T$ has the maximum possible size. Since the result might be very large, compute 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 10^4$). The description of the test cases follows.
The first line of each test case contains two integers $n$ and $m$ ($1 \le n \le 2 \cdot 10^5$, $0 \le m \le 2 \cdot 10^5$) — the maximum right endpoint of the segments, and the size of $S$.
The $i$-th of the next $m$ lines contains two integers $l_i$ and $r_i$ ($1 \le l_i \le r_i \le n$) — the boundaries of the segments in set $S$.
It is guaranteed that the given set $S$ is good, and the segments in set $S$ are pairwise distinct.
It is guaranteed that both the sum of $n$ and the sum of $m$ over all test cases do not exceed $2 \cdot 10^5$.
For each test case, output a single integer representing the number of different ways, modulo $998\,244\,353$, that you can add the maximum number of additional segments to set $S$ while ensuring that set $S$ remains good.
Input
Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.
The first line of each test case contains two integers $n$ and $m$ ($1 \le n \le 2 \cdot 10^5$, $0 \le m \le 2 \cdot 10^5$) — the maximum right endpoint of the segments, and the size of $S$.
The $i$-th of the next $m$ lines contains two integers $l_i$ and $r_i$ ($1 \le l_i \le r_i \le n$) — the boundaries of the segments in set $S$.
It is guaranteed that the given set $S$ is good, and the segments in set $S$ are pairwise distinct.
It is guaranteed that both the sum of $n$ and the sum of $m$ over all test cases do not exceed $2 \cdot 10^5$.
Output
For each test case, output a single integer representing the number of different ways, modulo $998\,244\,353$, that you can add the maximum number of additional segments to set $S$ while ensuring that set $S$ remains good.
6
1 0
2 3
1 1
2 2
1 2
5 2
1 3
2 3
4 1
1 1
6 2
1 3
4 6
2300 0
1
1
2
5
4
187997613
Note
In the first example, the only possible segment is $[1, 1]$, so $T = \{[1, 1]\}$ has the maximum size, and it is the only solution.
In the second example, it is not possible to add any additional segments to set $S$. Hence, the only way to add segments to $S$ is adding nothing.
In the third example, it is possible to add $7$ additional segments to $S$ while ensuring that the set remains good. It can be proven that adding more than $7$ additional segments to $S$ is not possible. There are exactly $2$ different ways to add these $7$ segments to $S$, and their respective sets $T$ are shown below:
- $\{[1, 1], [1, 3], [1, 4], [1, 5], [2, 2], [2, 3], [3, 3], [4, 4], [5, 5]\}$
- $\{[1, 1], [1, 3], [1, 5], [2, 2], [2, 3], [3, 3], [4, 4], [4, 5], [5, 5]\}$.
In the fourth example, there are exactly $5$ different ways to add a maximum of $6$ additional segments to $S$, and their respective sets $T$ are shown below:
- $\{[1, 1], [1, 2], [1, 3], [1, 4], [2, 2], [3, 3], [4, 4]\}$
- $\{[1, 1], [1, 2], [1, 4], [2, 2], [3, 3], [3, 4], [4, 4]\}$
- $\{[1, 1], [1, 3], [1, 4], [2, 2], [2, 3], [3, 3], [4, 4]\}$
- $\{[1, 1], [1, 4], [2, 2], [2, 3], [2, 4], [3, 3], [4, 4]\}$
- $\{[1, 1], [1, 4], [2, 2], [2, 4], [3, 3], [3, 4], [4, 4]\}$