题目描述

物理课上，小L和小K在做电学实验：“探究电阻两端的电压一定时，通过电阻的电流和电阻的大小的关系”。在这一实验中，控制电阻箱两端的电压为 $1~ V$ ，调节旋钮改变电阻箱的电阻，分别改为 $1 ~ \Omega , 2 ~ \Omega , 3 ~ \Omega , \ldots , n ~ \Omega $ ，分别读出对应的电流表示数为 $1 ~ A, \dfrac 1 2 ~ A , \dfrac 1 3 ~ A , ... ,\dfrac 1 n ~ A$ 。

在描述实验结论的时候，小L和小K产生了分歧。

小K：“众所周知，电阻两端的电压一定时，通过电阻的电流和电阻的大小成反比。也就是说，如果电阻箱两端电压保持不变，电阻箱的电阻为 $x ~ \Omega$ ，则通过电阻箱的电流为 $\dfrac 1 x ~ A$ 。”

小L：“但是我们为什么不可以用一个最高 $n-1$ 次的曲线去拟合它呢？”

为了改变小L的错误认识，小K决定先让 小L按自己的结论 去计算出电阻箱的电阻为 $(n+1) ~ \Omega$ 时，通过电阻箱的电流，然后进行实验，检验答案的正确性。同时，为了让小L更深刻地认识到自己的错误，小K决定进行多组实验，每组实验取不同的 $n$ 。

但是，小L在求解关于这 $n$ 组实验数据的最高 $n-1$ 次曲线时，遇到了问题。小L不想手算出这条曲线和曲线在 $(n+1) ~ \Omega$ 时的值，所以他找到了你，希望你能够求出这个值。

为了使运算更方便，小L将所有数据转化为取模 $998244353$ 意义下的整数值，你的输出也应该是这个整数值。但是，有时候数据的组数过多，导致实验数据或最后的运算结果没有意义，此时你需要输出 -1 。

输入格式

输入第一行有一个整数 $T$ ，表示进行了 $T$ 组实验。

每组实验一行，有一个整数 $n$ 。

输出格式

对于每组实验，输出 按照小L的结论 ，电阻箱电阻为 $(n+1) ~ \Omega$ 时对应的电流值。如果实验数据或求得的结果在模意义下没有定义，输出 -1 。

3
1
2
998244853

1
0
-1

提示

对于 $10\%$ 的数据， $1\le n\le 6$ 。

对于 $30\%$ 的数据， $1\le n\le 50$ 。

对于 $50\%$ 的数据， $1\le n\le 5000$ 。

对于 $70\%$ 的数据， $1\le n\le 10^5$ 。

对于 $100\%$ 的数据， $1\le T\le 100,1\le n\le 10^{18}$ 。