问题描述

给定一个正整数 n ，你可以做如下操作：

1. ​如果 n​ ​是偶数，则用 n / 2替换 n 。 ​
2. 如果 n​ ​是奇数，则可以用 n + 1或n - 1替换 n 。

返回 n​ ​变为 1 所需的 最小替换次数 。

格式

输入

输入一个正整数n

输出

次数

样例

8

3

7

4

4

2

提示

• 1 <= n <= 2^31 - 1