Collatz Sequence Length

In this problem, you are given an integer ( x ) and you need to compute the length of the sequence generated by the following process (often related to the Collatz conjecture):

• If \( x \) is even, then the next value of \( x \) is \( \frac{x}{2} \).
• If \( x \) is odd, then the next value of \( x \) is \( 3x+1 \).

The sequence terminates when ( x = 1 ), and the length of the sequence is defined as the number of terms from the initial value down to 1 (inclusive).

For example, if ( x = 6 ), the sequence is: 6, 3, 10, 5, 16, 8, 4, 2, 1, thus the length of the sequence is 9.

inputFormat

The first line contains an integer ( T ) (( 1 \leq T \leq 10^5 )), representing the number of test cases. Each of the following ( T ) lines contains a single integer ( x ) (( 1 \leq x \leq 10^6 )).

outputFormat

For each test case, output a single integer on a new line representing the length of the sequence for the given input number ( x ).## sample

3
6
7
15

9
17
18