题目描述

斐波那契数列的定义为：

$$\begin{cases} F_1 = 1 \\ F_2 = 1 \\ F_n = F_{n-1} + F_{n-2}, \quad n \geq 3 \end{cases} $$

给定整数 $n$，求 $F_n \pmod{998244353}$。

输入格式

第一行一个整数 $T$ ($1 \leq T \leq 1000$) — 测试数据的组数。

每组数据包含一个整数 $n$ ($1 \leq n \leq 10^4$)。

输出格式

对于每组数据，输出斐波那契数列的第 $n$ 项对 $998244353$ 取模后的结果。

样例

3
6
2
9

8
1
34