题目描述

设 \(f(x)\) 为在 \([1, 2x]\) 之间等概率随机选取一个整数得到的结果。

设初始有 \(x = 1\)，不断进行 \(x \leftarrow f(x)\) 的操作。给定 \(n\)，问 \(x\) 首次 \(\ge n\) 需要的期望操作次数。对 \(998244353\) 取模。

输入格式

第一行一个整数 \(T\) （\(1 \le T \le 10^5\)），表示询问次数。

之后 \(T\) 行，每行一个整数 \(n\) （\(1 \le n \le 10^6\)）（意义见上）。

保证所有测试点的 \(n\) 之和不超过 \(10^6\)。

输出格式

\(T\) 行，每行一个数表示答案。由于答案是有理数，请对 \(998244353\) 取模，即当答案为 \(\frac{p}{q}\) 时，输出 \(p \times q^{-1}\)，其中 \(q^{-1}\) 表示 \(q\) 对 \(998244353\) 的乘法逆元。

样例输入

3
1
2
20

样例输出

0
2
593354725

提示

样例解释

\(n = 1\) 时，不需要任何操作就有 \(x \ge n\)，因此答案是 0。

\(n = 2\) 时，只需要在 \(x = 1\) 的时候抽出 \(f(x) = 2\) 就能结束，否则一直 \(x = 1\)。设答案为 \(E\)，则 \(E = 1+\frac{1}{2}(E+0)\)，解得 \(E = 2\)。

\(n = 20\) 时，这里写不下。