# Hailstone Sequences

Given an integer $n$,
its *hailstone sequence* is constructed in the following
way. First, the integer $n$ is itself added as the first
number of the sequence. The following procedure is then
repeated. If the last integer $a$ added to the sequence is even, we
add $\frac{a}{2}$ to the
sequence. If it is odd, we add $3a + 1$ to the sequence. Whenever the
integer $1$ is added to
the sequence, the procedure concludes and the sequence
generated is the hailstone sequence of $n$.

For example, with $n = 7$, we get the sequence

\[ 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1 \]This has length $17$.

It is unknown if the hailstone sequence is finite for every
positive integer $n$.
Proving whether this is the case or not is known as the
$3n + 1$ problem, or the
*Collatz conjecture*. It has been proven that the
longest sequence among all $n \le
10^{12}$ has length 1349.

Given an integer $n$, determine the length of its hailstone sequence.

## Input

The input consists of an integer $n$ ($1 \le n \le 10^{12}$).

## Output

Output a single integer – the length of the sequence.

Sample Input 1 | Sample Output 1 |
---|---|

7 |
17 |