The 3n + 1 problem#419
Sign in

The 3n + 1 problem

1 second
128 megabytes
Very easy

Consider the following algorithm:

  1. Enter .

  2. Print .

  3. If n = 1, then STOP.

  4. If is odd, then n = 3 \cdot n + 1.

  5. Else, n = n / 2.

  6. Return to step 2.

Given the input , the following sequence of numbers will be printed:

22~11~34~17~52~26~13~40~20~10~5~16~8~4~2~1

It is conjectured that the above algorithm will terminate (when a is printed) for any positive integer . Despite the simplicity of the algorithm, it is unknown whether this conjecture is true. However, it has been verified for all integers such that 0 < n < 1,000,000 (and, in fact, for many more numbers as well).

For a given , the number of values printed in its sequence (including the ) is called the cycle length of . In the example above, the cycle length for is .

For any two integers and , find the maximum cycle length for all numbers between and inclusive.

Input

The input consists of a series of pairs of integers and , one pair per line. All integers will satisfy 0 < i < 1,000,000 and 0 < j < 1,000,000. You may assume that no operation will cause overflow of a -bit integer.

Output

For each pair of integers and , print and in the same order as in the input, followed by the maximum cycle length for numbers between and inclusive. For each test case, print three numbers on one line, separated by single spaces.

Examples

Example 1

Loading
Loading