Collatz Sequence Length

You are given a positive integer \(N\). Generate a sequence using the following rules: if \(N\) is even, then \(N\) becomes \(\frac{N}{2}\) (i.e. if \(N \equiv 0 \pmod{2}\)); if \(N\) is odd, then \(N\) becomes \(3N+1\). This process is repeated until \(N\) becomes 1.

Your task is to output the length of this sequence including both the starting number and the final number 1.

For example, if \(N = 6\), the sequence is: 6, 3, 10, 5, 16, 8, 4, 2, 1, so the length is 9.

inputFormat

The first line contains an integer \(T\), representing the number of test cases. Each of the next \(T\) lines contains a positive integer \(N\).

outputFormat

For each test case, output the length of the Collatz sequence on a separate line.

3
6
1
16

9
1
5