The hailstone sequence is formed in the following way:

If n is even, divide it by 2 to get n'

if n is odd, multiply it by 3 and add l to get n'

It is conjectured that for any positive integer number n, the sequence will always end in the repeating cycle: 4, 2, 1, 4, 2, 1,.... Suffice to say, when n = = 1, we will say the sequence has ended.

Write a program to determine the largest value in the sequence for a given n.

Input

The first line of input contains a single integer P, (1$ \le$P$ \le$100000), which is the number of data sets that follow. Each data set should be processed identically and independently.

Each data set consists of a single line of input consisting of two space separated decimal integers. The first integer is the data set number. The second integer is n, (l$ \le$n$ \le$100, 000), which is the starting value.

Output

For each data set there is a single line of output consisting of the data set number, a single space, and the largest value in the sequence starting at and including n.

Sample Input

4

1 1

2 3

3 9999

4 100000

Sample Output

1 1

2 16

3 101248

4 100000

PLEASE C++

INDENT THE CODE And comment it.

**Subject Computer Science C-Family Programming**