Cặp số

Xét một cặp số nguyên dương $(a,b)$. Từ cặp $(a,b)$, trong một bước ta có thể chuyển sang một trong hai cặp mới:

• $(a+b,b)$
• $(a,a+b)$

Ban đầu ta có cặp $(1,1)$. Hãy tìm số bước ít nhất $k$ để biến đổi cặp $(1,1)$ thành một cặp mà trong đó có ít nhất một số bằng $n$.

Dữ liệu vào

Một số nguyên duy nhất $n$.

Dữ liệu ra

In ra một số nguyên duy nhất $k$, là số bước ít nhất cần thực hiện.

Ràng buộc

• $1\le n\le {10}^6$

Ví dụ