Putata 和 Budada 正在玩一个有趣的游戏。他们使用一个有 $n$ 个面的骰子进行游戏。每个面分别写有 $0$ 到 $n-1$ 之间的整数，掷骰子时，每个面朝上的概率相等。换句话说，掷骰子的结果是 $0$ 到 $n-1$ 之间的一个均匀随机整数。

游戏分为两轮。第一轮中，发生以下情况： * Putata 掷骰子并得到一个整数结果，记为 $x$。

第二轮中，Budada 可以选择执行以下操作之一： 结束游戏，此时游戏得分为 $x$。 再掷一次骰子，记结果为 $y$，游戏结束，此时游戏得分为 $x \oplus y$。 这里 $\oplus$ 表示二进制异或运算。

Putata 和 Budada 想要最大化游戏得分，并且他们非常聪明，总是会做出最优选择。请编写一个程序，对于给定的 $n$，计算游戏得分的期望值。

可以证明答案可以表示为一个不可约分数 $\frac{x}{y}$，其中 $x$ 和 $y$ 为整数且 $y \not\equiv 0 \pmod{998\,244\,353}$。请输出等于 $x \cdot y^{-1} \pmod{998\,244\,353}$ 的整数。换句话说，输出一个满足 $0 \le a < 998\,244\,353$ 且 $a \cdot y \equiv x \pmod{998\,244\,353}$ 的整数 $a$。

输入格式

输入包含多个测试用例。第一行包含一个整数 $T$ ($1 \le T \le 10^4$)。 接下来的 $T$ 行，每行包含一个整数 $n$ ($1 \le n \le 998\,244\,352$)，表示一个询问。

输出格式

输出 $T$ 行，每行表示一个测试用例的答案。

样例

输入 1

4
1
2
3
4

输出 1

0
249561089
776412276
2