暂无测试数据。

斐波那契数列的定义为：$$\displaystyle \begin{aligned} & fib_0 = 1 \\ & fib_1 = 1 \\ & fib_i = Fib_{i-1} + Fib_{i-2},(i\geq 2) \end{aligned} $$

已知任意自然数 $x$ 均可以通过若干个 不同的 斐波那契数相加得到，其中$fib_0$ 和 $fib_1$ 是两个不同的斐波那契数。现在定义斐波那契表示 $F(x)$ 表示若干个 不同的 斐波那契数相加得到自然数 $x$ 的一组相加的方案。例如 $$\displaystyle \begin{aligned} & F(7) = 5 + 2 = fib_4 + fib_2\\ & F(7) = 5 + 1 + 1 = fib_4 + fib_1 + fib_0 \\ & F(7) = 3 + 2 + 1 + 1 = fib_3 + fib_2 + fib_1 + fib_0 \end{aligned} $$表示 $7$ 对应有 至少三个斐波那契表示。

定义斐波那契表示的贡献为 $w(F(x))$ ：对于自然数 $x$ 的所有表示方案 $F(x)$ 中每个数字的积。例如：$F(7) = 5,2$，那么 $w(F(7)) = 5 \times 2 = 10$。

现在给出自然数 $n$，请你求出 $n$ 的 所有斐波那契表示 的贡献的和。

例如 $n = 7$，答案：$(5\times 2) +(5 \times 1 \times 1) + (3 \times 2 \times 1 \times 1) = 21$

输入格式

第一行一个整数 $T(1\leq T \leq 10^6)$，表示共有 $T$ 组数据。

接下来 $T$ 行，每行一个整数 $n(1\leq n \leq 10^7)$，表示一个自然数。

输出格式

输出共 $T$ 行，每行一个整数，依次表示每组数据的答案。由于答案可能过大，所以答案对 $998244353$ 取模。

注意：由于本题输入输出量较大，建议使用scanf/printf进行输入输出避免超时。

数据范围

对于 $10%$ 的数据，$n\leq 10$；

对于另外 $20%$ 的数据，$n\leq 100$；

对于另外 $20%$ 的数据，$n \leq 10^5, T = 1$；

对于 $100%$ 的数据，$1\leq T \leq 10^6,1\leq n \leq 10^7$。

3
1
2
7

2
3
21