Asterism Stream

• 时间限制：3 秒
• 内存限制：256 MiB

题目描述

Bogocubic 正在和 amenotiomoi 玩一个游戏。首先，Bogocubic 固定了一个整数 $n$，然后他给 amenotiomoi 一个整数 $x$，初始时 $x=1$。

每一步，amenotiomoi 以相同的概率执行以下两种操作之一：

• 将 $x$ 增加 $1$；
• 将 $x$ 乘以 $2$。

Bogocubic 想要知道，amenotiomoi 需要进行多少步操作，才能使 $x$ 大于等于 $n$ 的期望步数。请你帮他计算这个期望步数对 $998\,244\,353$ 取模的结果。

形式化地，设 $M=998\,244\,353$。可以证明答案可以表示为最简分数 $\frac{p}{q}$，其中 $p$ 和 $q$ 是整数且 $q \not\equiv 0 \pmod{M}$。请输出等于 $p \cdot q^{-1} \bmod M$ 的整数。换句话说，输出一个整数 $y$，满足 $0 \le y < M$ 且 $y \cdot q \equiv p \pmod{M}$。

输入格式

每组测试数据包含多个测试用例。第一行包含测试用例数 $t$（$1 \le t \le 100$）。
接下来每个测试用例一行，包含一个整数 $n$（$1 \le n \le 10^{18}$）。

输出格式

对于每个测试用例，输出一个整数，表示期望步数对 $998\,244\,353$ 取模的结果。

样例输入 1

7
1
4
8
15
998244353
296574916252563317
494288321850420024

样例输出 1

0
499122179
717488133
900515847
93715054
44488799
520723508

提示

在第一个测试用例中，$n\le x$，无需任何操作，所以答案为 $0$。

在第二个测试用例中，对于 $n=4$，所有可能的操作序列及其概率如下：

• $1\stackrel{+1}{\longrightarrow}2\stackrel{+1}{\longrightarrow}3\stackrel{+1}{\longrightarrow}4$，概率为 $\frac{1}{8}$；
• $1\stackrel{\times 2}{\longrightarrow}2\stackrel{+1}{\longrightarrow}3\stackrel{+1}{\longrightarrow}4$，概率为 $\frac{1}{8}$；
• $1\stackrel{+1}{\longrightarrow}2\stackrel{+1}{\longrightarrow}3\stackrel{\times 2}{\longrightarrow}6$，概率为 $\frac{1}{8}$；
• $1\stackrel{\times 2}{\longrightarrow}2\stackrel{+1}{\longrightarrow}3\stackrel{\times 2}{\longrightarrow}6$，概率为 $\frac{1}{8}$；
• $1\stackrel{+1}{\longrightarrow}2\stackrel{\times 2}{\longrightarrow}4$，概率为 $\frac{1}{4}$；
• $1\stackrel{\times 2}{\longrightarrow}2\stackrel{\times 2}{\longrightarrow}4$，概率为 $\frac{1}{4}$。

因此，期望步数为 $4 \cdot \left(3 \cdot \frac{1}{8}\right) + 2 \cdot \left(2 \cdot \frac{1}{4} \right) =\frac{5}{2} \equiv 499122179 \pmod{998244353}$。

在第三个测试用例中，对于 $n=8$，期望步数为 $\frac{137}{32}\equiv 717488133\pmod{998244353}$。

在第四个测试用例中，对于 $n=15$，期望步数为 $\frac{24977}{4096} \equiv 900515847 \pmod{998244353}$。

数据范围

对于所有数据，$1\le t\le100$，$1\le n\le10^{18}$。

每个测试点独立计分。