Collatz Conjecture Steps

The Collatz Conjecture is a famous unsolved problem in mathematics. In this problem, you are given a positive integer n and you need to determine how many steps it takes to reduce n to 1 using the following process:

If \( n = 1 \), stop. Otherwise, if n is even, replace n with \( \frac{n}{2} \); if n is odd, replace n with \( 3n+1 \). Count each replacement as one step.

For example, starting with 6, the sequence is: 6, 3, 10, 5, 16, 8, 4, 2, 1 which takes 8 steps.

inputFormat

The input is given via standard input (stdin). The first line contains an integer T, the number of test cases. Each of the following T lines contains a single positive integer n.

outputFormat

For each test case, output the number of steps required to reach 1 in the Collatz sequence on a separate line. The output should be written to standard output (stdout).

## sample

3
6
19
27

8
20
111

</p>