Collatz Sequence Length

In this problem, you are given a positive integer \(n\). Your task is to compute the length of the sequence generated by repeatedly applying the following rules until the number becomes 1:

• If \(n\) is even, replace \(n\) with \(\frac{n}{2}\).
• If \(n\) is odd, replace \(n\) with \(3n + 1\).

The length of the sequence is defined as the total number of terms including the starting number and 1. For example, if \(n=6\), the sequence is: 6, 3, 10, 5, 16, 8, 4, 2, 1, so the answer is 9.

Note: It is conjectured (the Collatz conjecture) that this sequence always terminates at 1 for any positive integer \(n\), although a formal proof is not known.

inputFormat

The input consists of a single line containing an integer \(n\) \( (1 \leq n \leq 10^6) \) read from standard input (stdin).

outputFormat

Output a single integer — the length of the sequence generated by applying the given rules until the number becomes 1. The output should be printed to standard output (stdout).

6

9