Another Cow Number Game

No attempts yetTime limit1sMemory limit128 MB

Problem

The cows are playing a silly number game again. Bessie is tired of losing and wants you to help her cheat.

In this game, a cow supplies an integer $N$ ($1 \le N \le 1{,}000{,}000$). This is move 0. Then the following rules are repeated:

  • If $N$ is odd, multiply $N$ by 3 and add 1 ($N \leftarrow 3N + 1$).
  • If $N$ is even, divide $N$ by 2 ($N \leftarrow N / 2$).

Each time the number is multiplied or divided, the score increases by one point. The game ends -- and the score is finalized -- when $N$ becomes 1. If $N$ is initially 1, the score is 0.

Here is an example with $N$ starting at 5:

        N     Next Value    Comment    Score
        5        16          3*5+1       1
       16         8           16/2       2
        8         4            8/2       3
        4         2            4/2       4
        2         1            2/2       5

The final score is 5.

Input

  • Line 1: A single integer $N$

Output

  • Line 1: A single integer, the score for this game when starting at $N$