问题描述

斐波那契数列是一个经典的数列，定义如下：

$F_0 = 0,\quad F_1 = 1$

对于所有整数 $n \ge 2$，有：

$F_n = F_{n-1} + F_{n-2}$

现在给定多个查询，每个查询给出一个整数 $n$，请你计算第 $n$ 项斐波那契数 $F_n$，并输出其对 $998244353$ 取模的结果。

输入格式

第一行包含一个整数 $T$，表示查询次数。

接下来 $T$ 行，每行包含一个整数 $n$，表示需要查询的斐波那契数列的第 $n$ 项。

输出格式

输出 $T$ 行，每行一个整数，表示对应查询的结果：

$F_n \bmod 998244353$

样例输入

5
0
1
2
5
10

样例输出

0
1
1
5
55

说明

斐波那契数列前几项为：

$0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, \dots$

例如：

第 $5$ 项为 $5$

第 $10$ 项为 $55$

评测数据规模

对于所有数据，满足：

$1 \le T \le 1000$

$0 \le n \le 100000$