Description

In physics class, Xiao L and Xiao K are doing an electrical experiment: “Exploring the relationship between the current through a resistor and the resistance value when the voltage across the resistor is fixed.” In this experiment, they keep the voltage across the resistance box at $1~ V$, and adjust the knob to change the resistance of the box to $1 ~ \Omega , 2 ~ \Omega , 3 ~ \Omega , \ldots , n ~ \Omega$. They then read the corresponding current values as $1 ~ A, \dfrac 1 2 ~ A , \dfrac 1 3 ~ A , ... ,\dfrac 1 n ~ A$.

When describing the experimental conclusion, Xiao L and Xiao K disagree.

Xiao K: “As everyone knows, when the voltage across a resistor is fixed, the current through the resistor is inversely proportional to the resistance. That is, if the voltage across the resistance box stays unchanged and the resistance is $x ~ \Omega$, then the current through it is $\dfrac 1 x ~ A$.”

Xiao L: “But why can’t we use a curve of degree at most $n-1$ to fit it?”

To correct Xiao L’s misunderstanding, Xiao K decides to first let Xiao L compute according to his own conclusion the current through the resistance box when its resistance is $(n+1) ~ \Omega$, and then perform an experiment to check whether the answer is correct. Meanwhile, to make Xiao L realize his mistake more deeply, Xiao K decides to do multiple experiments, each with a different $n$.

However, when Xiao L tries to find the degree at most $n-1$ curve for these $n$ experimental data points, he runs into difficulties. Xiao L does not want to manually compute this curve and its value at $(n+1) ~ \Omega$, so he asks you to compute this value.

To make calculations easier, Xiao L converts all data into integers under modulo $998244353$, and your output should also be this integer value. However, sometimes there are too many data points, causing the experimental data or the final computed result to be meaningless. In this case, you should output -1.

Input Format

The first line contains an integer $T$, indicating that $T$ experiments were conducted.

Each experiment consists of one line containing an integer $n$.

Output Format

For each experiment, output according to Xiao L’s conclusion the current value when the resistance box has resistance $(n+1) ~ \Omega$. If the experimental data or the computed result is not defined under the modulo meaning, output -1.

3
1
2
998244853

1
0
-1

Hint

For $10\%$ of the testdata, $1\le n\le 6$.

For $30\%$ of the testdata, $1\le n\le 50$.

For $50\%$ of the testdata, $1\le n\le 5000$.

For $70\%$ of the testdata, $1\le n\le 10^5$.

For $100\%$ of the testdata, $1\le T\le 100, 1\le n\le 10^{18}$.

Translated by ChatGPT 5