Interesting Parenthesis

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.

• Select two indices $i, j (1 \le i,j \le 2n)$ and swap $s[i]$ and $s[j]$.

You have to calculate the number of different interesting parentheses sequence of length $2n$, and print it modulo $998244353$.

Input

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.

Output

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$.

Sample

Input	Output
3 1 2 100	2 6 829549001

In the first test case, there are $2$ interesting parentheses sequence, these are as follows.

1. $()$

2. $)($

In the second test case, there $6$ interesting parentheses sequence, these are as follows.

1. $(())$

2. $()()$

3. $())($

4. $)(()$

5. $)()($

6. $))(($