题目背景

Special for beginners, ^_^

题目描述

在一座古老的宝藏迷宫里，有一串神秘的数字。

守护者告诉你一个规则：

如果数字 n 是偶数 → 下一步变成 n / 2

如果数字 n 是奇数 → 下一步变成 3×n + 1

重复这个过程，直到数字变成 1 为止。

现在给你一个整数 n，请你用递归的方法求：

从 n 变到 1 一共需要多少步。

（变成 1 时不再继续）

输入格式

一个整数 n，满足 $1\le n\le 10^6$。

输出格式

输出一个整数，表示变成 1 所需要的步数。

样例

6

8

样例解释

6 → 3 → 10 → 5 → 16 → 8 → 4 → 2 → 1 共 8 步