Cho một số nguyên dương ~N~ ~(1 \le N \le 10^{18})~. Để biến đổi số ~N~ thành số ~1~ có thể thực hiện bằng cách sử dụng các phép toán sau đây:

• Phép toán ~1~: Nếu ~N~ là số chẵn, em chia ~N~ cho ~2~;
• Phép toán ~2~: Nếu ~N~ là số lẻ, em có thể trừ đi ~1~ hoặc cộng thêm ~1~;

Yêu cầu

Em hãy viết chương trình tìm số bước ít nhất để biến đổi ~N~ về ~1~ (có thể có nhiều cách khác nhau để đạt được số bước ít nhất).

Dữ liệu đầu vào

Gồm số nguyên dương ~N~.

Dữ liệu đầu ra

Gồm một số nguyên duy nhất là số bước ít nhất để biến đổi ~N~ thành ~1~.

Ví dụ

Ví dụ 1

INPUT

15

OUTPUT

5

Giải thích: Gồm ~5~ bước:

• ~15 \rightarrow 16~ (cộng ~1~)
• ~16 \rightarrow 8~ (chia ~2~)
• ~8 \rightarrow 4~ (chia ~2~)
• ~4 \rightarrow 2~ (chia ~2~)
• ~2 \rightarrow 1~ (chia ~2~)