The Fibonacci Sequence is a mathematical sequence where the first and second terms are 1, and each term after that is the sum of the two previous terms. More formally, if $f_i$ denotes the $i^{\text{th}}$ term of the Fibonacci Sequence, then $f_1=f_2=1$, and $f_k=f_{(k-1)}+f_{(k-2)}$ for all integer $k>2$.

The modulo (or $mod$) operation is an operation represented by the $\mathrm{\%}$ symbol. The expression $a\mathrm{\%}b$ denotes the remainder when the positive integer $a$ is divided by the positive integer $b$. For example, $7\mathrm{\%}2=1$, because the remainder when $7$ is divided by $2$ is $1$. The modulo operator is available in most programming languages using the operator % - for example, the line int a = 7%2; in C++ will set a to be 1.

You have found yourself at the first house of a long street. There are a total of $N$ houses along this street, numbered $1$ to $N$. You are trying to travel from the first house to the last house as fast as possible.

You can always walk from one house to an adjacent house (i.e. from house $w$ to house $w-1$ or house $w+1$, if they exist). This takes one minute.

At each house, there is also a trampoline that allows you to travel a larger distance. In particular, at the $i^{\text{th}}$ house, there is a trampoline with strength $a_i$. Using the trampoline also takes one minute, and from house $i$, you can use the trampoline to jump either backwards to house $i-a_i$ (as long as $i-a_i\ge 1$) or forwards to house $i+a_i$ (as long as $i+a_i\le N$).

You have been able to reverse-engineer a pattern of the values of $a_i$ for all the houses:

$a_i=(f_i\mathrm{\%}2021)+(i\mathrm{\%}50)$ for all $1\le i\le N$,

where $f_i$ represents the $i^{\text{th}}$ term in the Fibonacci Sequence and $\mathrm{\%}$ represents the modulo operation, as defined at the beginning of the problem.

For reference purposes, $a_1=2$, $a_2=3$, $a_3=5$, $a_4=7$, $a_5=10$, $a_6=14$, $a_7=20$, and $a_{125}=356$.

Please find the minimum number of minutes you need to travel from house $1$ to house $N$.

NOTE FOR PYTHON USERS: If your program receives TLE (time limit exceeded), you should try submitting using the PyPy interpreter: when you are submitting your code, try using "PyPy 3" or "PyPy 2" as the language, instead of "Python 3" or "Python 2".

Input Specification

The input will consist of one integer, $N$, the number of houses on the street.

Output Specification

Please output the minimum number of minutes you need to travel from house $1$ to house $N$.

Constraints and Partial Marks

For $3$ of the $10$ available marks, $N\le 400$.

For the remaining $7$ marks, $N\le 5\cdot {10}^5$.

Sample Input 1

9

Sample Output 1

3

Explanation for Sample Output 1

The first $9$ terms of the sequence $a_i$ are $2,3,5,7,10,14,20,29,43$. To travel from house $1$ to house $9$, the optimal pattern of moves is:

• Move $1$: Jump from house $1$ to house $3$. This is possible as $1+a_1=1+2=3$.
• Move $2$: Jump from house $3$ to house $8$. This is possible as $3+a_3=3+5=8$.
• Move $3$: Walk from house $8$ to house $9$. This is possible as $8+1=9$.

Every move takes $1$ minute, so the output is 3.

Sample Input 2

27

Sample Output 2

4

Explanation for Sample Output 2

One way to reach house $27$ in $4$ moves is as follows:

• Move $1$: Jump from house $1$ to house $3$. This is possible as $1+a_1=1+2=3$.
• Move $2$: Jump from house $3$ to house $8$. This is possible as $3+a_3=3+5=8$.
• Move $3$: Walk backwards from house $8$ to house $7$. This is possible as $8-1=7$.
• Move $4$: Jump from house $7$ to house $27$. This is possible as $7+a_7=7+20=27$.