Kevin逛超市

题号：NC253623
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

氧气少年在逛超市。

他总共买了 $n$ 件物品，当他走到超市出口时，出口的报警器响了起来。

已知恰好有一件物品使报警器报警，并且这件使报警器报警的物品于 $n$ 件物品中随机分布。现在氧气少年想找出这件使报警器报警的物品，他采取这样的方式找出这件物品：

将这 $n$ 件物品标号为 $1\dots n$ 。

定义集合 $S$ 中最小的元素为 $S_{\min}$ ， $S$ 中最大的元素为 $S_{\max}$ ， $S$ 包含的元素数量为 $|S|$ 。

氧气少年先将所有物品的编号放入集合 $A$ ，即令集合 $A=\lbrace 1,2,\cdots n \rbrace$ 。然后他会进行下面的操作：

令集合 $B=\lbrace A_{\min},A_{\min}+1\cdots \lfloor \frac{A_{\min}+A_{\max}}{2} \rfloor\rbrace$ ，然后执行步骤 2；
将集合 $B$ 中对应编号的物品通过报警器。

如果报警，并且 $|B|=1$ ，则结束；
如果报警，并且 $|B|>1$ ，则令 $A=B$ ，然后回到步骤 1；
如果没报警，则令集合 $A=\lbrace \lfloor \frac{A_{\min}+A_{\max}}{2}\rfloor+1, \lfloor \frac{A_{\min}+A_{\max}}{2}\rfloor+2\cdots A_{\max}\rbrace$ ，然后回到步骤 1。

氧气少年想知道，从他开始查找物品开始，到他找到这件物品为止，氧气少年将物品通过报警器的次数（即：步骤 2 执行次数）的期望。

可以证明，答案可以表示成 $\frac{p}{q}$ 的形式。其中， $p\geq 0,q\geq 1,\gcd(p,q)=1,q\mod 998244353\neq 0$ 。因此你只需输出 $p\cdot q^{998244351}\mod 998244353$ 即可。

输入描述:

第一行包含一个整数 ，表示测试用例的组数。

对于每组测试用例：

仅输入一行，包含一个整数 ，表示物品的数量。保证 。

输出描述:

对于每组测试用例：

仅输出一行，包含一个整数，表示答案。

示例1

输入

复制

输出

复制

1
499122178
332748120

说明

对于第一组测试用例：

如果  号物品是让报警器报警的物品，那么次数为 ，概率为 。期望为 。。

对于第二组测试用例：

如果  号物品是让报警器报警的物品，那么次数为 ，概率为 ；如果  号物品是让报警器报警的物品，那么次数为 ，概率为 。期望为 。。

对于第三组测试用例：

如果  号物品是让报警器报警的物品，那么次数为 ，概率为 ；如果  号物品是让报警器报警的物品，那么次数为 ，概率为 ；如果  号物品是让报警器报警的物品，那么次数为 ，概率为 。期望为 。。