C. Lucky Sequence
time limit per test
3 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

A number sequence $$$[a_1, a_2, \ldots, a_n]$$$ is lucky if and only if the following requirements are fulfilled.

  • Each element $$$a_i$$$ in the sequence is a non-negative integer such that $$$0 \leq \frac{a_i}{i} \lt \frac{\sqrt{5} + 1}{2}$$$;
  • For any two elements $$$a_i$$$ and $$$a_j$$$ $$$(i \neq j)$$$ in the sequence, $$$a_i \neq 0$$$ and $$$a_j \neq 0$$$ imply that $$$a_i \neq a_j$$$.

Your task is to figure out how many number sequences of length $$$n$$$ are lucky and report the number modulo $$$998\,244\,353$$$.

Input

The first line contains an integer $$$T$$$ $$$(1 \leq T \leq 10^5)$$$, indicating the number of test cases.

Then follow $$$T$$$ test cases. For each test case:

The only line contains an integer $$$n$$$ $$$(1 \leq n \leq 10^5)$$$, indicating the length of the sequence.

Output

For each test case, output an integer in one line, representing the number of lucky sequences of length $$$n$$$ modulo $$$998\,244\,353$$$.

Example
Input
5
1
2
3
4
5
Output
2
7
27
141
919
Note

For $$$n = 2$$$, there are $$$7$$$ lucky sequences: $$$[0, 0]$$$, $$$[0, 1]$$$, $$$[0, 2]$$$, $$$[0, 3]$$$, $$$[1, 0]$$$, $$$[1, 2]$$$ and $$$[1, 3]$$$.