F. Random Walk
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

There is an infinitely large $$$2$$$-dimensional grid. Initially, you are at $$$(0,0)$$$, and there is a set $$$S=\{(0,0)\}$$$. You will walk exactly $$$n$$$ steps on the grid. In each step:

  • Suppose you are currently at $$$(x,y)$$$. You will walk to one of the following four positions with equal probability: $$$(x+1,y)$$$, $$$(x-1,y)$$$, $$$(x,y+1)$$$, $$$(x,y-1)$$$. Let your new position be $$$\left(x',y'\right)$$$. Then, add $$$\left(x',y'\right)$$$ to $$$S$$$.

Compute the expected size of $$$S$$$ after $$$n$$$ steps.

Formally, let $$$M = 998\,244\,353$$$. It can be shown that the exact answer can be expressed as an irreducible fraction $$$\frac{p}{q}$$$, where $$$p$$$ and $$$q$$$ are integers and $$$q \not \equiv 0 \pmod{M}$$$. Output the integer equal to $$$p \cdot q^{-1} \bmod M$$$. In other words, output such an integer $$$x$$$ that $$$0 \le x \lt M$$$ and $$$x \cdot q \equiv p \pmod{M}$$$.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 2 \cdot 10^5$$$). The description of the test cases follows.

The only line of each test case contains an integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$).

Note that there is no restriction on the sum of $$$n$$$ over all test cases.

Output

For each test case, output the expected size of $$$S$$$.

Example
Input
4
1
2
3
114514
Output
2
249561091
499122180
340469626