Problem Description

Given a sequence of length $n$, denoted as $a_1, a_2, \ldots, a_n$, initially $a_i = i$. Perform $n-1$ operations on this sequence, where the $i$-th operation involves selecting an integer $j$ uniformly at random from the range $[1, n-i]$, and then setting $a_j$ to $a_j + 2a_{n-i+1}$.

Determine the expected value of $a_1$ after all operations, modulo $998244353$.

Input Format

The first line of input contains a positive integer $T$ $(1 \leq T \leq 10^4)$, representing the number of test cases.

Following this, $T$ lines each contain a positive integer $n$ $(1 \leq n \leq 10^9)$, indicating the length of the sequence.

Output Format

Output $T$ lines, each containing an integer representing the expected value of $a_1$ modulo $998244353$.

Sample Input and Output

Sample Input #1

3
4
2
5

Sample Output #1

30
5
55

Sample Input #2

3
4
3
5

Sample Output #2

30
14
55

Sample Input #3

3
8
1
3

Sample Output #3

204
1
14

见题面 Input 部分

见题面 Output 部分