The famous Collatz sequence is generated by a method decribed as follows. Given a positive integer N, if it is odd, then replace it with 3*N+1. For even number N, use N/2 instead. You can get a sequence of number by this method. It is conjectured that the algorithm above will terminate at 1 for any integral input value. Despite the simplicity of the algorithm, it is unknown whether this conjecture is true. It has been verified, however, for all integers n such that 0 < n < 1,000,000 (and, in fact, for many more numbers than this.)

-Input

The first line contains a single integer T tells that there are T cases in the problem. Then for each case, there is an integers N.



Output

For each number N, output the sequence generated in a line, using coma as its separator.