HAILSTONE - Hailstone

The following algorithm produces what is know as the hailstone sequence:

  • Pick some positive integer and call it n.
  • If n is even, divide it by two.
  • If n is odd, multiply it by three and add one.
  • Continue this process until n is equal to one.

For any given input value of n, the numbers will go up and down, but eventually—at least for all numbers that have ever been tried—comes down to end in 1. In some respects, this process is reminiscent of the formation of hailstones, which get carried upward by the winds over and over again before they finally descend to the ground. Because of this analogy, this sequence of numbers is usually called the Hailstone Sequence, although it goes by many other names as well. Call the length of this sequence the Hailstone Length.

Your problem is to calculate the maximum hailstone length between two given numbers. Report only the input value that produces the maximum output.

Input

The first line of input will give the number of test cases (a positive integer, 1 ≤ t ≤ 100. Each t successive lines will have two integers, 1 ≤ a ≤ 100,000,000 and 1 ≤ b ≤ 100,000,000, that represent the range from which to calculate the maximum hailstone length.

Output

The value of n that has the maximum hailstone sequence length between a and b.

Example

Input:
2
1 10
20 25

Output:
9
22

Added by:Nathan
Date:2015-10-29
Time limit:1s-5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU JS-MONKEY
Resource:From Douglas Hofstadter’s Pulitzer-prize-winningbook Gödel, Escher, Bach

hide comments
2018-06-06 08:22:26
Sequence lengths for 20..25 are 8, 8, 16, 16, 11, 24, so going by example case we should consider only the numbers literally "between" a and b, or in open interval (a, b). Assuming this gives WA though, as well as [a,b] and [a,b).

Psetter, please check the testfiles or clarify the statement.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.