Catwalk BrainF**k

The esoteric programming language BrainF**k is written using only the eight characters +-][><,..

• > : Increase the pointer by $1$.
• < : Decrease the pointer by $1$.
• + : Increase the value at the current pointer by $1$.
• - : Decrease the value at the current pointer by $1$.
• . : Output the value at the current pointer as an ASCII character.
• , : Read one character and overwrite the value at the current pointer with its ASCII code.
• [ : If the byte at the current pointer is $0$, jump to the matching ].
• ] : If the byte at the current pointer is not $0$, jump to the matching [.

The characters [ and ] denote the beginning and end of loops. Compilation fails if and only if these brackets are not properly matched.

A cat walks on the keyboard. At every step, it types one uniformly random character from +-][><,..

Given an integer $N$, find the probability that the length-$N$ string typed after exactly $N$ steps can be compiled as BrainF**k code.

The input is given from Standard Input in the following format:

$T$ $\mathrm{case}_1$ $\mathrm{case}_2$ $\vdots$ $\mathrm{case}_T$

Each case is given in the following format:

$N$

For each test case, print the answer on one line.

Write the probability for that test case as a reduced fraction $\cfrac{p}{q}$. The denominator $q$ is not divisible by $998\,244\,353$. Let $q^{-1}$ be the multiplicative inverse of $q$ modulo $998\,244\,353$. Print

as an integer between $0$ and $998\,244\,352$, inclusive.

• $1 \le T \le 200\,000$.
• $1 \le N \le 100\,000$.