Problem Description

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

After all operations are finished, compute the expected value of $a_1 \bmod\text{ }998244353$.

Input Format

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

The next $T$ lines each contain a positive integer $n$ $(1 \leq n \leq 10^9)$, representing the length of the sequence.

Output Format

Output $T$ lines. Each line contains one integer, the expected value of $a_1 \bmod\text{ }998244353$.

3
4
2
5

30
5
55

3
4
3
5

30
14
55

3
8
1
3

204
1
14

Hint

Translated by ChatGPT 5