Hailstone HOTPO

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 $1$ 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 contains the number of data sets $t(1\le t\le 10^5)$ 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(1\le n\le 10^5)$, which is the starting value.

Output

For each data set print a single line consisting of the data set number, one space, and the largest value in the sequence starting from $n$.

Examples