#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/contests/14/problems/F

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░██████████████████████████████████████████

Connected Interval Prefixes - Repovive Standard Round 5 | Repovive | Repovive

14F. Connected Interval Prefixes

3000 pts1s256 MB

You are given $n$ closed intervals on the real line. The endpoints of every interval are integers between $1$ and $n$ .

A permutation $p_1, p_2, \ldots, p_n$ of the intervals is called good if for every $k$ with $1 \le k \le n$ , the union of intervals $p_1, p_2, \ldots, p_k$ is connected.

Equivalently, for every prefix, the union must be a single closed interval on the real line.

For each test case, count the number of good permutations modulo $998244353$ .

Constraints

$1 \le t \le 100$
$1 \le n \le 3000$
The sum of $n^2$ over all test cases is at most $9 \times 10^6$ .
$1 \le l_i \le r_i \le n$

Input

t

\left. \begin{array}{l} n \\ l_1 \quad r_1 \\ l_2 \quad r_2 \\ \vdots \\ l_n \quad r_n \end{array} \right\} \times t

Output

\left. \begin{array}{l} ans \end{array} \right\} \times t

Samples

Input

Case 1

1
1 1

Case 2

2
1 1
2 2

Case 3

Case 4

Case 5

Explanation

Case 1

There is only one interval, so the only permutation is good.

Case 2

After both intervals are chosen, the union contains two separate points and is not connected. Therefore no permutation is good.

Case 3

Every two intervals intersect, so any order keeps every prefix connected. There are $3! = 6$ good permutations.

Case 4

If $[1,3]$ is first, the other two intervals can be placed in any order. If a single-point interval is first, $[1,3]$ must be second. This gives $2 + 1 + 1 = 4$ good permutations.

Case 5

There are $4! = 24$ permutations in total. The only bad ones are the four permutations where $[1,2]$ and $[3,4]$ are the first two intervals in either order, because the second prefix is disconnected. So the answer is $20$ .

Output

Case 1

Case 2

Case 3

Case 4

Case 5

You are given $n$ closed intervals on the real line. The endpoints of every interval are integers between $1$ and $n$ .

A permutation $p_1, p_2, \ldots, p_n$ of the intervals is called good if for every $k$ with $1 \le k \le n$ , the union of intervals $p_1, p_2, \ldots, p_k$ is connected.

Equivalently, for every prefix, the union must be a single closed interval on the real line.

For each test case, count the number of good permutations modulo $998244353$ .

$1 \le t \le 100$
$1 \le n \le 3000$
The sum of $n^2$ over all test cases is at most $9 \times 10^6$ .
$1 \le l_i \le r_i \le n$

t

\left. \begin{array}{l} n \\ l_1 \quad r_1 \\ l_2 \quad r_2 \\ \vdots \\ l_n \quad r_n \end{array} \right\} \times t

\left. \begin{array}{l} ans \end{array} \right\} \times t

Every two intervals intersect, so any order keeps every prefix connected. There are $3! = 6$ good permutations.

If $[1,3]$ is first, the other two intervals can be placed in any order. If a single-point interval is first, $[1,3]$ must be second. This gives $2 + 1 + 1 = 4$ good permutations.

	#	Title	Points	Solved	Admin

	#	Title	Points	Solved	Admin

	#	Title	Points	Solved	Admin

	#	Title	Points	Solved	Admin

Commentary

My submissions

Sponsors

Ranking

Commentary

My submissions

Sponsors

Ranking

Commentary

My submissions

Sponsors

Ranking

Commentary

My submissions

Sponsors

Ranking

14F. Connected Interval Prefixes

Constraints

Input

Output

Samples

14F. Connected Interval Prefixes

Constraints

Input

Output

Samples