COLL - The Collatz Sequence

An algorithm given by Lothar Collatz produces sequences of integers, and is described as follows:

Step 1: Choose an arbitrary positive integer A as the first item in the sequence. 

Step 2: If A = 1 then stop. 

Step 3: If A is even, then replace A by A / 2 and go to step 2. 

Step 4: If A is odd, then replace A by 3 * A + 1 and go to step 2.


It has been shown that this algorithm will always stop (in step 2) for initial values of A as large as 109. In this problem we want to determine the length of the sequence that includes all values produced until either the algorithm stops (in step 2).

Input

A number representing A (1 <= A <= 1,000,000,000).

Output

The length of the sequence generated by A.

 

Example

Input:
10

Output:
6

Explanation of sample input:

10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1 (the sequence is of length 6)

Added by:Omar ElAzazy
Date:2011-12-13
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=635

hide comments
2018-07-01 10:31:05
ANSWER FOR THE GIVEN TEST CASE IS 7.

2016-08-15 00:46:03 isaac
The output in the example is not correct.It is not 6 it is 7,which includes the input together.As i submitted with the example i got a wrong answer.So be careful while handling the things
2012-02-13 13:31:04
missing 8 in explanation

Last edit: 2011-12-20 16:17:37
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.