一个数字序列 $[a_1, a_2, \dots, a_n]$ 被称为“幸运序列”，当且仅当它满足以下条件：

• 序列中的每个元素 $a_i$ 都是非负整数，且满足 $0 \le \frac{a_i}{i} < \frac{\sqrt{5}+1}{2}$；
• 对于序列中任意两个元素 $a_i$ 和 $a_j$ ($i \neq j$)，若 $a_i \neq 0$ 且 $a_j \neq 0$，则 $a_i \neq a_j$。

你的任务是计算长度为 $n$ 的幸运序列的数量，并将结果对 $998\,244\,353$ 取模。

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 10^5$)，表示测试用例的数量。 接下来是 $T$ 个测试用例。每个测试用例： 仅包含一行，为一个整数 $n$ ($1 \le n \le 10^5$)，表示序列的长度。

输出格式

对于每个测试用例，输出一行一个整数，表示长度为 $n$ 的幸运序列的数量，对 $998\,244\,353$ 取模。

样例

样例输入 1

5
1
2
3
4
5

样例输出 1

2
7
27
141
919

说明

对于 $n = 2$，共有 7 个幸运序列：$[0, 0], [0, 1], [0, 2], [0, 3], [1, 0], [1, 2]$ 和 $[1, 3]$。