28175번 - Dice Game 다국어

문제

Putata and Budada are playing an interesting game. They play this game with a die having $n$ faces. Every integer between 0ドル$ and $n-1$ are written on exactly one face, and when they roll this die, each side will face up with equal probability. In other words, rolling the die will result in a uniform random integer between 0ドル$ and $n-1$ with equal probability.

The game has two rounds. In the first round, the following happens:

• Putata will roll the die and get an integer as the result, say $x$.

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

• End the game, and the score of the game will be $x$.
• Roll the die again, let the result be $y,ドル and the game will end, the score of the game will be $x \oplus y$. Here $\oplus$ denotes binary exclusive-or operation.

Putata and Budada want to maximize the score of the game, and they are so clever that they will always make the best choice. Please write a program to calculate, for some given $n,ドル the expectation of the score of the game.

It can be shown that the answer can be expressed as an irreducible fraction $\frac{x}{y},ドル where $x$ and $y$ are integers and $y \not \equiv 0 \pmod {998,244円,353円}$. Output the integer equal to $x\cdot y^{-1}\pmod {998,244円,353円}$. In other words, output such an integer $a$ that 0ドル\leq a < 998,244円,353円$ and $a\cdot y\equiv x\pmod {998,244円,353円}$.

입력

The input contains several test cases. The first line contains an integer $T$ (1ドル \leq T\leq 10^4$).

For the following $T$ lines, each line contains an integer $n$ (1ドル\leq n\leq 998,244円,352円$), denoting one question.

출력

Output $T$ lines, each line denotes the answer for one test case.

제한

힌트