最少步数

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

给定一个数字n,我们可以进行3种操作,加1,减1,如果可以整除2,还可以除2,问最少多少步变换到1.

Input

 输入数据的第一行包含数字n(1<=n<=10000000)。多组输入。

Output

 计算结果。

Sample Input

3

Sample Output

2

Hint

 

Source

cz