Counting Is Not Fun (Easy Version)

This is the easy version of the problem. The only difference is that this version has smaller limits on $t$ and $n$. You can hack only if you solved all versions of this problem.

Now Little John is rich, so he finally buys a house big enough to fit himself and his favorite bracket sequence. But somehow he ended up with a lot of brackets! Frustrated, he penetrates the ceiling with the "buddha palm".

A bracket sequence is called balanced if it can be constructed by the following grammar.

1. The empty sequence $\varnothing$ is balanced.
2. If the bracket sequence $A$ is balanced, then $\mathtt{(}A\mathtt{)}$ is also balanced.
3. If the bracket sequences $A$ and $B$ are balanced, then the concatenation $AB$ is also balanced.

For example, "(())()", "()", "(()(()))", and the empty sequence are balanced, while "(()" and "(()))(" are not.

Given a balanced bracket sequence $s$, a pair of indices $(i,j)$ with $i<j$ is called a good pair if $s_i$ is (, $s_j$ is ), and the two brackets were added together by Rule 2 while building $s$. For example, "(())()" has three good pairs: $(1,4)$, $(2,3)$, and $(5,6)$. Every balanced bracket sequence of $2n$ brackets has exactly $n$ good pairs, and any order of applying the rules to build the same sequence gives the same set of good pairs.

Emily plays a bracket guessing game with John. John has a balanced bracket sequence $s$ with $n$ good pairs, and Emily does not know it. John tells Emily the value of $n$ and asks her to guess the sequence. Over $n$ turns, John gives one clue per turn:

• $l\,r$: the sequence $s$ contains the good pair $(l,r)$.

The clues are pairwise distinct and do not contradict each other.

At some point Emily can be certain that only one balanced bracket sequence matches the clues so far. For example, suppose Emily knows $s$ has $3$ good pairs and contains the good pair $(2,5)$. Of the $5$ balanced bracket sequences with $3$ good pairs, only "((()))" contains $(2,5)$, so Emily does not need all $n$ turns.

After each turn, Emily wants to know how many balanced bracket sequences match the clues so far. Counting these is hard when there are many good pairs. Help her: before and after each turn, find the count modulo $998\,244\,353$.

Each test contains multiple test cases. The first line contains $t$ ($1 \le t \le 10^3$), the number of test cases. The first line of each test case contains $n$ ($2 \le n \le 5000$), the number of good pairs. Then $n$ lines follow, and the $i$-th of them contains two integers $l_i$ and $r_i$ ($1 \le l_i < r_i \le 2n$), the $i$-th clue.

The clues in one test case are pairwise distinct and do not contradict each other. The sum of $n$ over all test cases does not exceed $5000$.

For each test case, output $n+1$ integers on one line. The first integer is the count before any clue. For each $i \ge 1$, the $(i+1)$-th integer is the count after the $i$-th clue. All values are modulo $998\,244\,353$.

The first test case of the sample is explained in the statement. The third test case is explained as follows. There are $132$ balanced bracket sequences with $6$ good pairs. After the first clue $(2,3)$, there are $42$ sequences with that good pair. After the second clue $(1,6)$, there are $5$ sequences with good pairs $(2,3)$ and $(1,6)$. After the third clue $(7,8)$, there are $2$ sequences with those three good pairs: "(()())()(())" and "(()())()()()". After the fourth clue $(9,12)$, only "(()())()(())" remains. The counts after the fifth and sixth clues are both $1$, since the content of $s$ is already known.