Collatz Sequence Length

Source: Phước Hưng OJ

Version: Phuoc Hung OJ Extended

Problem Statement

Start with a positive integer $n$ and record it as $x=n$. While $x\ne1$, replace $x$ by $x/2$ when it is even, or by $3x+1$ when it is odd, and record the new value. Stop when 1 is reached. Count the number of recorded terms, including both the initial $n$ and the final 1. Do not print the sequence.

Input

One line contains one positive integer $n$.

Output

Print one integer: the number of terms in the Collatz sequence from $n$ through 1.

Subtasks

• Subtask 1 (20%): $1\le n\le20$.
• Subtask 2 (30%): $1\le n\le1000$.
• Subtask 3 (50%): $1\le n\le10^6$.

Examples

Example 1

Input:

1

Output:

1

Explanation: The initial value already equals 1. No transformation occurs, but the sequence contains one term: 1.

Example 2

Input:

6

Output:

9

Explanation: The recorded terms are 6, 3, 10, 5, 16, 8, 4, 2, 1. There are eight transformations but nine terms.

Example 3

Input:

3

Output:

8

Explanation: The sequence is 3, 10, 5, 16, 8, 4, 2, 1, containing eight terms.