时间限制： 1.0 秒

空间限制： 256 MB

题目描述

定义 Hailstone 序列为：

$$Hailstone(n) = \begin{cases} \{1\}, & n \le 1 \\ \{n\} \cup Hailstone(\dfrac n2), & n~is~even \\ \{n\} \cup Hailstone(3n + 1), & n~is~odd \end{cases} $$

例如，当 $n = 42$ 时，对应的 Hailstone 序列为：

$$42,21,64,32,16,8,4,2,1$$

当 $n = 7$ 时，对应的 Hailstone 序列为：

$$7,22,11,34,17,52,26,13,40,20,10,5,16,8,4,2,1$$

给定初始的 $n$，求对应的 Hailstone 序列的长度。

输入格式

从标准输入读入数据。

第一行为一个正整数 $T~(1 \le T \le 1000)$，表示输入的行数。

接下来 $T$ 行，每行一个正整数 $n~(1 \le n \lt 2^{64})$，为初始值。

输出格式

输出到标准输出。

对于每个输入，输出一行对应的 Hailstone 序列的长度。

2
42
7

9
17

提示

Chap 01 绪论，习题 [1-29]。

虽然“Hailstone 序列长度必然有限”的结论尚未得到证明，无法被称之为真正的算法，但是本题数据范围下的序列长度都是有限的。

注意一下数据范围，unsigned long long 是否能正确表示中间结果？可以看看 "A+B Problem ?" 当中提到的 128 位整数~

请注意，128 位整数需要自己定义输入和输出方式，具体可以看习题解析 [4-6] 的 readNumber 实现。