Story

It seems $N$ is large this time.

Problem Statement

For a balanced parenthesis sequence $T$, let $f(T)$ be the value of $x$ after performing the following procedure.

• Initially, let $S$ be the empty set and $x=0$, and do the following for $i=1, 2, \cdots, N$ in this order.
  • If $T_i=$(, add $i$ to $S$.
  • If $T_i=$), let $j$ be the largest element contained in $S$, and add to $x$ the number of occurrences of () as a substring in the string obtained by extracting the open interval $(j, i)$ of $T$. Then, remove $j$ from $S$.

For example, $f($()(())$)=1, f($(()()())$)=3$.

You are given a positive integer $N$. Find the sum of $f(S)$ over all possible strings that are balanced parenthesis sequences $S$ of length $N$.
Since the answer can be very large, find it modulo $998244353$.

You are given $T$ cases; answer each of them.

Input

$T$
$case_1$
$case_2$
$\vdots$
$case_T$

$case_i$ represents the $i$-th case and is given in the following format.

$N$

• $1\leq T\leq 10^5$
• For each case, $1\leq N\leq 10^6$

Output

Output $T$ lines. On the $k(1\leq k\leq T)$-th line, output the answer for the $k$-th case.
For each case, let $r$ be the sum of $f(S)$ modulo $998244353$, and output it in the following format.

$r$

Print a newline at the end.

Sample

3
4
2
11

1
0
0