CLTZ - Collatz

Let N be a positive integer, Consider the following recurrence: f(1) = N and f(K) = (0.5 + 2.5 * (f(K-1) mod 2)) * f(K-1) + (f(K-1) mod 2) if K>1. For a given N you have to compute the smallest L for which f(L)=1 (such an L always exists for N's in the input).

Input

Each line contains a positive integer N in decimal notation. You can be sure that N and all intermediate results are not bigger than 10^1888. Input terminated by EOF.

Output

For each number N in the input print one line with the value of L in decimal notation.

Example

Input:
1
2
321
1111111111111
111111111111111111111111111111111111111111111111111111111111

Output:
1
2
25
261
1296

Added by:czylabsonasa
Date:2005-04-25
Time limit:1.983s
Source limit:18000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:Folklore

hide comments
2022-07-31 03:19:36
but the brute force in python is RE and I can't use python
2018-12-05 16:46:08
Use python or java....it will make ur life easy
2013-06-22 20:04:36 Punit Singh Koura
can someone suggest some tricky test cases. I am getting wrong answer but i dont know why.
2011-09-06 21:55:16 Muhammad Ridowan
Its from unproven Collatz conjecture. So probably there is no O(1) type solution.
2011-09-06 21:55:16 刘启鹏
i guess that brute force algorithm is enough for the problem.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.