Bogocubic 正在和 amenotiomoi 玩游戏。首先,Bogocubic 固定了一个整数 $$$n$$$,然后他给 amenotiomoi 一个整数 $$$x$$$,它最初等于 $$$1$$$。
在一步中 amenotiomoi 以相同的概率执行以下操作之一:
- 将 $$$x$$$ 增加 $$$1$$$;
- 将 $$$x$$$ 乘以 $$$2$$$。
Bogocubic 想要找到让 $$$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}$$$。