Counting Valid Permutations

You are given a positive integer \( n \). Consider the sequence \( f(n) \) defined by:

\( f(1)=1, \quad f(2)=1, \quad f(n)=f(n-1)+f(n-2) \) for \( n\geq3 \).

In other words, \( f(n) \) follows the Fibonacci recurrence. Your task is to compute \( f(n) \) modulo \( 998244353 \). This number, which represents the count of valid permutations under the given (hidden) constraints, must be output for each test case.

The problem involves multiple test cases. For each test case, read an integer \( n \) and output \( f(n) \) modulo \( 998244353 \).

inputFormat

The input is read from standard input. The first line contains an integer \( T \) representing the number of test cases. Each of the following \( T \) lines contains a single integer \( n \) (\( 1 \leq n \leq 10^9 \) or a reasonable bound based on the intended solution).

outputFormat

For each test case, output one line containing the value of \( f(n) \) modulo \( 998244353 \).

## sample

4
1
2
3
4

1
1
2
3

</p>