Immensely Long Expressions

You own an artificial intelligence company that builds math-related chat bots. Usually things run smoothly, but today they do not. All of the AI-related machines have crashed, and to make matters worse, today is the day of the well-known annual International Competition on Preposterous Calculations (ICPC).

During the ICPC, participants often use your company's services to find the exact value of arithmetic expressions. This year is no different. The contest has already sent you a huge number of queries, but you cannot answer them right now.

Each query asks for the exact value of an arithmetic expression, a string of exactly $n$ characters. Here $n$ is odd, and the string satisfies the following conditions.

• The string consists only of the digits 0 to 9 and the arithmetic operation signs '+', '-', '*', and '/'.
• The characters at odd positions (1st, 3rd, ..., $n$-th) are digits, and the rest are operation signs.
• A '/' sign is never immediately followed by the digit 0.

For example, '1*2/3+4-5', '0', and '9/2' satisfy these conditions for some values of $n$. '23-5', '-7', '5/0', and '998244353' do not.

The value of an expression follows the usual precedence rules. First, all multiplications and divisions are performed from left to right. Then all additions and subtractions are performed from left to right.

Assume that every expression satisfying the conditions above is equally likely to be the next query. What is the expected value of the result?

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

Each of the next $T$ lines contains a single odd integer $n$ ($1 \leq n < 10^{18}$), the length of the expression.

For each test case, print a single integer $R$ ($0 \leq R < 998\,244\,353$). If the expected value is the irreducible fraction $\frac{P}{Q}$, then $P \equiv QR \pmod{998\,244\,353}$. The expected value is always a rational number for any $n$, and such an $R$ always exists.

The answers for the first three test cases are $\dfrac{9}{2}$, $\dfrac{170\,929}{21\,840}$, and $\dfrac{25\,555\,213\,441}{2\,146\,435\,200}$, respectively.