U637527 再战斐波那契

对于一个正整数序列 $A = (A _ 1, A _ 2, \ldots, A _ m)$，定义其权值为 $\displaystyle \prod _ {i = 1} ^ m Fib (A _ i)$。 其中 $Fib (x)$ 是斐波那契数列，满足递推式 $$Fib (x) = \begin {cases} 0 & x = 0 \\ 1 & x = 1 \\ Fib (x - 1) + Fib (x - 2) & x \ge 2 \end {cases}$$ 给你一个数 $n$，你需要计算满足 $\sum A _ i = n$ 的正整数序列 $A$ 的权值之和，答案对 $998244353$ 取模。

第一行包含一个整数 $T$，表示数据组数。 对于每组数据，一行包含一个整数 $n$。

对于每组数据，输出答案对 $998244353$ 取模的值。

#### 样例 #1 解释 对于第一组数据，合法的序列只有 $(1)$，价值之和为 $1$。 对于第二组数据，合法的序列有 $(1, 1), (2)$，价值之和为 $1 + 1 = 2$。 对于第三组数据，合法的序列有 $(1, 1, 1, 1), (1, 1, 2), (1, 2, 1), (2, 1, 1), (1, 3), (3, 1), (2, 2), (4)$，价值之和为 $1 + 1 + 1 + 1 + 2 + 2 + 1 + 3 = 12$。 #### 数据范围 对于所有数据，$1 \le T \le 2 \times 10 ^ 5$，$1 \le n \le 3 \times 10 ^ 7$。 各测试点分值均等。 |测试点编号|$T \le$|$n \le$| |:-:|:-:|:-:| |$1 \sim 3$|$3$|$8$| |$4 \sim 5$|^|$20$| |$6 \sim 9$|^|$5000$| |$10 \sim 14$|^|$2 \times 10 ^ 5$| |$15 \sim 19$|^|$3 \times 10 ^ 7$| |$20 \sim 25$|$2 \times 10 ^ 5$|^|