Số fibonacci là số có dạng:

~F_1 = 1~

~F_2 = 1~

~F_N = F_{N-1} + F_{N-2}~

Nhập vào số nguyên dương ~N~. In ra số fibonacci lớn nhất mà bé hơn hoặc bằng ~N~.

Input

• Nhập vào số nguyên dương ~N~ (~1 \leq N \leq 10^5~).

Output

• In ra số fibonacci lớn nhất mà bé hơn hoặc bằng ~N~.

Example

Input

6

Output

5