角谷猜想

题目描述

日本一位中学生发现了一个奇妙的定理，请角谷教授证明，而教授无能为力，于是产生了角谷猜想。

猜想内容如下：

给定任意一个自然数：

• 如果它是偶数，则将它除以 2；
• 如果它是奇数，则将它乘以 3 再加 1；

得到一个新的自然数后，继续按照上述规则进行计算。经过若干次运算后，结果一定会变为 1。

请编写程序验证该猜想：输入一个正整数 n，求经过多少次运算可以得到自然数 1。

例如，输入 22，变化过程如下：

22 / 2 = 11
11 * 3 + 1 = 34
34 / 2 = 17
17 * 3 + 1 = 52
52 / 2 = 26
26 / 2 = 13
13 * 3 + 1 = 40
40 / 2 = 20
20 / 2 = 10
10 / 2 = 5
5 * 3 + 1 = 16
16 / 2 = 8
8 / 2 = 4
4 / 2 = 2
2 / 2 = 1

因此，22 经过 15 次运算后得到自然数 1。

输入格式

一行，一个正整数 n。

数据范围：

1 <= n <= 20000

输出格式

一行，一个整数，表示从 n 变为 1 所需要的运算次数。

样例输入 1

22

样例输出 1

15

提示

当输入为 1 时，已经是自然数 1，因此需要的运算次数为 0。