Do You Like Interactive Problems?

There is an integer $x$ satisfying $1 \leq x \leq n$. You know $n$ but you don't know $x$.

You can do the following guessing: pick an random integer $y$ uniformly satisfying $1 \leq y \leq n$ (your $y$ may equal to previous queries), and you will be told if $x < y, x > y or x = y$. You will stop asking if there is only one possible $x$ satisfying all the conditions.

Given $n$, if $x$ is picked randomly uniformly, what's your expected number of queries?

Input

The first line contains an integer $T \: (1 \leq T \leq 100)$ denothing the number of test cases.

For each test case, the only line contains an integer $n \: (1 \leq n \leq 10^9)$.

Output

For each test case, output one integer denoting the expected number of queries modulo $998244353$.

Formally, it can be proven that the sought expected value can be represented as an irreducible fraction $p/q$ which satisfies $q \not \equiv 0 \bmod 998244353$, and there is a unique integer $r$ satisfies $0 \leq r < 998244353$ and $qr \equiv p \mod 998244353$. Find this $r$.

Example

2
1
2

0
1