# HDU-6198 number number number

## Problem Description

We define a sequence F:

⋅ F0=0,F1=1;

⋅ Fn=Fn−1+Fn−2 (n≥2).

Give you an integer k, if a positive number n can be expressed by n=Fa1+Fa2+…+Fak where 0≤a1≤a2≤⋯≤ak, 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.

## Input

There are about 500 test cases, end up with EOF.
Each test case includes an integer k which is described above. (1≤k≤1000000000)

## Output

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

1

4