#P18591. Dice Game

Dice Game

Dice Game

有一枚公平的 nn 面骰子,骰面上的数字依次为 0,1,…,n−10,1,\ldots,n-1。每次掷骰得到各数字的概率均为 1/n1/n,两次结果相互独立。

游戏首先掷一次骰子,得到 xx。看到 xx 后,可以选择以下一种操作:

  • 立即结束,得分为 xx;
  • 再掷一次,得到 yy 后结束,得分为 x⊕yx\mathbin{\oplus}y。

其中 ⊕\oplus 是按位异或。若选择第二种操作,不能在看到 yy 后撤销或改选第一种操作。

双方合作使最终得分的数学期望尽可能大。对每个给定的 nn,求采用最优决策时的期望得分,并对 998244353998244353 取模。

输入格式

第一行给出整数 TT,表示询问数。

接下来 TT 行,每行一个整数 nn。

数据范围为 1≤T≤100001\le T\le10000、1≤n≤9982443521\le n\le998244352。

输出格式

对每个 nn 输出一行一个整数,为对应期望在模 P=998244353P=998244353 意义下的值。

具体地,将期望写为最简分数 u/vu/v。数据保证 vv 不是 PP 的倍数,输出 u⋅v−1 mod Pu\cdot v^{-1}\bmod P,取值为 0,1,…,P−10,1,\ldots,P-1。

样例输入 1

4
1
2
3
4

样例输出 1

0
249561089
776412276
2