Dice Game

Putata and Budada are playing a game with a die that has $n$ faces. Every integer from $0$ to $n-1$ is written on exactly one face, and each face is equally likely to land up. In other words, a roll gives a uniform random integer between $0$ and $n-1$.

The game has two rounds. In the first round, Putata rolls the die and gets an integer $x$.

In the second round, Budada can choose one of the following:

• End the game. The score is $x$.
• Roll the die again and let the result be $y$. The game ends, and the score is $x \oplus y$, where $\oplus$ is the bitwise exclusive-or operation.

Putata and Budada want to maximize the score, and both always make the best choice. For a given $n$, compute the expected score of the game.

The answer can be written as an irreducible fraction $\frac{x}{y}$ with $y \not\equiv 0 \pmod{998\,244\,353}$. Output the integer $a$ with $0 \leq a < 998\,244\,353$ and $a \cdot y \equiv x \pmod{998\,244\,353}$.

The first line contains an integer $T$ ($1 \leq T \leq 10^4$). Each of the next $T$ lines contains an integer $n$ ($1 \leq n \leq 998\,244\,352$), which is one query.

Output $T$ lines. Line $i$ contains the answer for the $i$-th query.