Problem Description

We define a sequence $F$:

$\cdot$ $F_0=0, F_1=1$;
$\cdot$ $F_n=F_{n-1}+F_{n-2}\ (n\geq 2)$.

Give you an integer $k$, if a positive number $n$ can be expressed by
$n=F_{a_1}+F_{a_2}+...+F_{a_k}$ where $0\leq a_1 \leq a_2 \leq \dots \leq a_k$, this positive number is $mjf-good$. Otherwise, this positive number is $mjf-bad$.
Now, give you an integer $k$, you task is to find the minimal positive $mjf-bad$ number.
The answer may be too large. Please print the answer modulo 998244353.

Input

There are about 500 test cases, end up with EOF.
Each test case includes an integer $k$ which is described above. ($1\leq k \leq 10^9$)

Output

For each case, output the minimal $mjf-bad$ number mod 998244353.

1

4