Parentheses sequence of length $2n$ is the sequence containing exactly $n$ opening parentheses $«(»$ and exactly $n$ closing parentheses $«)»$
A parentheses sequence is called balanced if one can turn it into a valid math expression by adding characters $«+»$ and $«1»$. For example, sequences $«(())()»$, $«()»$ and $«(()(()))»$ are balanced, while $«)(»$, $«(()»$ and $«(()))(»$ are not.
A parentheses sequence, $s$ of length $2n$ is called interesting if one can turn it balanced by doing the following operation at most once.
You have to calculate the number of different interesting parentheses sequence of length $2n$, and print it modulo $998244353$.
First line will contain $T ( 1 \le T \le 10^3 )$, the number of test cases. Each of the next $T$ lines will contain one integer $n (1 \le n \le 10^3)$, half the length of the interesting parentheses sequence.
For each testcase, print one line containing an integer $ans (0 \le ans \lt 998244353)$, which is the number of different interesting parentheses sequence modulo $998244353$.
Input | Output |
---|---|
3 1 2 100 | 2 6 829549001 |
In the first test case, there are $2$ interesting parentheses sequence, these are as follows.
$()$
$)($
In the second test case, there $6$ interesting parentheses sequence, these are as follows.
$(())$
$()()$
$())($
$)(()$
$)()($
$))(($