Maximum 0ccurrences

You are given an integer $n$ and you have to do one operation at a time:

$1.$ If $n$ is odd, you must multiple it by $3$ and add $1$ to the result.

$2.$ If $n$ is even, you must divide it by $2$.

What is the number with maximum occurrences if you do $10^{100}$ operations on the given number $n$?

Input data

The first line of the input will contain $t$, the number of test cases.

Each of the next $t$ lines will contain a single number $n$.

Output data

On each line of the output we will print an integer, representing the answer to the problem. If there are multiple solutions, print the biggest one of them.

Constraints and Clarifications

• $1 \leq n \leq 10^{18}$
• $1 \leq t \leq 10^5$
• For tests worth $50$ points, $1 \leq n \leq 1 \ 000$.

Example 1

stdin

3
2
18
1

stdout

2
4
1

Explanation

For the first sample test case, the numbers printed will be $2$, $1$, $4$, $2$, $1$, $\dots$, and therefore $2$ and $1$ will show up one more time than the other numbers. Since we need to print the biggest integer, then we will print $2$.