Consider two binary arrays A and B, each of size N and $a permutation^\dagger P$ of length N.

You will make two new arrays C and D, each of size N, such that:

C_{i}=A_{P_{i}} (1 ≤ i ≤ N)
D_{i}=B_{P_{i}} (1 ≤ i ≤ N)

Let us define:
The score of the permutation P as $\min(\text{LNDS}(C),\text{LNDS}(D))$, where $\text{LNDS}(X)$ gives the length of longest $non-decreasing subsequence^{\ddagger}$ of X.
F(A,B) as the maximum score over all possible N! permutations P.

Find $\sum_{x \in$ $S} \sum_{y \in$ S}{F(x,y)}, where S contains all binary arrays of size N(|S|=2^{N}).

Since sum might be large, please print it modulo 998244353.

$^\dagger A$ permutation of length N consists of all integers from 1 to N exactly once. For example, [4,2,3,1] is a permutation, while [1,2,2] is not a permutation.

$^{\ddagger} A sequence A$ is a subsequence of a sequence B if A can be obtained from B by deletion of several (possibly, zero or all) elements. For example, [3,1] is a subsequence of [3,2,1], [4,3,1] and [3,1], but not [1,3,3,7] and [3,10,4].

------ Input Format ------

• The first line of input will contain a single integer T, denoting the number of test cases.
• The only line of each test case contains a single integer N, where N should be the length of the binary arrays.

------ Output Format ------

For each test case, output on a new line, the sum modulo 998244353.

------ Constraints ------

$1 ≤ T ≤ 1000$
$1 ≤ N ≤ 2000$
- The sum of $N$ over all test cases won't exceed $2 \cdot 10^{3}$.

----- Sample Input 1 ------
5
1
2
3
4
343

----- Sample Output 1 ------
4
30
174
914
857794275

----- explanation 1 ------
Test case $1$:
$\
F(0,0) = 1 \
F(0,1) = 1 \
F(1,0) = 1 \
F(1,1) = 1$

Test case $2$: $S=[00,01,10,11]$. So we have $16$ pairs of $(x,y)$.

$F(00,00) = 2 \
F(00,10) = 2 \
F(00,01) = 2 \
F(00,11) = 2 \
F(10,00) = 2 \
F(10,10) = 2 \
F(10,01) = 1 \
F(10,11) = 2 \
F(01,00) = 2 \
F(01,10) = 1 \
F(01,01) = 2 \
F(01,11) = 2 \
F(11,00) = 2 \
F(11,10) = 2 \
F(11,01) = 2 \
F(11,11) = 2$

To get maximum score for pair $(11,10)$, we can take $P=[2,1]$.

Now $C=[1,1]$ and $D=[0,1]$. Thus, maximum score is $2$.

Test case $3$: $S = [000, 001, 010, 011, 100, 101, 110, 111]$.

Consider $A = 001, B = 110,$ and a random $P = [2, 3, 1]$. Thus, $C$ and $D$ can be generated as :
- $C = A_{P_{1}}A_{P_{2}}A_{P_{3}} = A_{2A}_3A_{1} = 010$.
The longest non-decreasing subsequence are $00$ or $01$, each having length $2$.
- $D = B_{P_{1}}B_{P_{2}}B_{P_{3}} = B_{2B}_3B_{1} = 101$.
The longest non-decreasing subsequence is $01$, having length $2$.

Thus, score of $P = [2, 3, 1]$ is $2$ over $A = 001$ and $B = 110$. Similarly, we find the sores of all permutations of length $3$ over $A$ and $B$ and set $F(A, B)$ as maximum out of those.

见题面

见题面