CF2063F1 Counting Is Not Fun (Easy Version)

This is the easy version of the problem. The difference between the versions is that in this version, the limits on $ t $ and $ n $ are smaller. You can hack only if you solved all versions of this problem. Now Little John is rich, and 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 through the ceiling with the "buddha palm".A bracket sequence is called balanced if it can be constructed by the following formal 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 concatenated sequence $ A B $ is also balanced. For example, the sequences "(())()", "()", "(()(()))", and the empty sequence are balanced, while "(()" and "(()))(" are not. Given a balanced bracket sequence $ s $ , a pair of indices $ (i,j) $ ( $ i

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 10^3 $ ). The description of the test cases follows. The first line of each test case contains one integer $ n $ ( $ 2 \le n \le 5000 $ ) — the number of good pairs. Then, each of the $ n $ following lines contains two integers $ l_i $ and $ r_i $ representing the $ i $ -th clue ( $ 1 \le l_i < r_i \le 2n $ ). The clues in one test case are pairwise distinct and do not contradict each other. It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 5000 $ .

For each test case, output $ n+1 $ integers on a separate line: - The first integer is the answer before all clues, modulo $ 998\,244\,353 $ . - For all $ i \ge 1 $ , the $ i+1 $ -th integer is the answer after the $ i $ -th clue, modulo $ 998\,244\,353 $ .

The first test case of the example is explained in the problem description. The third test case of the example is explained as follows. It can be shown that there are $ 132 $ balanced bracket sequences with $ 6 $ good pairs. The answers after each clue are given as follows: 1. You are given the good pair $ (2,3) $ . There are $ 42 $ balanced bracket sequences having the good pair $ (2,3) $ . 2. You are given the good pair $ (1,6) $ . There are $ 5 $ balanced bracket sequences having good pairs $ (2,3) $ , $ (1,6) $ . 3. You are given the good pair $ (7,8) $ . There are $ 2 $ balanced bracket sequences having the three good pairs. The strings are "(()())()(())" and "(()())()()()", respectively. 4. You are given the good pair $ (9,12) $ . There is only one balanced bracket sequence having the four good pairs. The content of $ s $ is therefore the only string, which is "(()())()(())". Then, the number of bracket sequences after the fifth and the sixth clue are both $ 1 $ as you already know the content of $ s $ .