Hailstone Sequence

The hailstone sequence is defined as follows:

• If $n$ is even, divide it by $2$.
• If $n$ is odd, multiply it by $3$ and add $1$.

The hailstone (Collatz) conjecture states that if you start the sequence from any positive integer $n$, it always ends in the cycle $4, 2, 1, 4, 2, 1, \ldots$. In this problem, the sequence is considered finished as soon as it reaches $1$.

Given $n$, write a program that finds and prints the largest value in this sequence. The starting value $n$ itself counts as part of the sequence, so for $n = 1$ the answer is $1$.

The first line contains the number of test cases $T$ ($1 \le T \le 100{,}000$). Each of the next $T$ lines contains one starting value $n$ ($1 \le n \le 100{,}000$) of a hailstone sequence.

For each test case, print the largest value in the hailstone sequence that starts at $n$.