Migrated from Lutece 2740 Debutante Waltz

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

纯音乐，请您欣赏。

——《Debutante Waltz》

---

对于一个 $01$ 串 $s$（即只包含 $0$ 和 $1$ 的字符串），我们总可以把它写成 $kp+p'$ 的形式。其中 $kp$ 表示顺序连接 $k$ 个字符串 $p$。$p'$ 是 $p$ 的一个前缀（可以为空串）。$+p'$ 表示把字符串 $p'$ 直接连接在 $kp$ 的后面。

我们称字符串 $s$ 的循环节 $p$ 为当忽略 $p'$ 时，使得 $k$ 最大且非空的 $p$，而这个字符串的值 $v(s)$ 就是 $k$。例如 $v(01001001)=2$，因为 $01001001$ 可以写成 $2(010)+01$。$v(11111)=5$，因为 $11111$ 可以写成 $5(1)$，$p'$ 为一空串。

现在给定 $n$，请计算所有长度恰好为 $n$ 的 $01$ 字符串的值的和。由于答案很大，请输出它对 $998244353$ 取模后的值。

Input

第一行包含一个整数 $T\ (1\le T\le 100)$，表示数据组数。

接下来 $T$ 行，每行包含一个整数 $n\ (1\le n\le 10^9)$。

保证对于每组数据，都有 $\sum n\le 10^{10}$。

Output

对于每组数据，输出一行一个整数，表示答案对 $998244353$ 取模后的值。

Samples

5
1
2
3
114
514

2
6
12
954037435
530871613

Note

对于 $n=3$，

$$\begin{aligned} &v(000)+v(001)+v(010)+v(011)+v(100)+v(101)+v(110)+v(111)\\ &=3+1+1+1+1+1+1+3\\ &=12\\ \end{aligned} $$

Resources

2022 UESTC ICPC Training for Math and Geometry