Problem D
Collatz Conjecture

Let $a$ be a positive integer and consider the sequence where $x_0=a$ and

The Collatz conjecture states that this sequence will always reach $1$.

For example, if $a=10$, then $x_0=10,x_1=5,x_2=16,x_3=8,x_4=4,x_5=2$ and $x_6=1$.

Write a program that reads a positive integer from the user and, using a while loop, outputs each element of the above sequence until it reaches $1$.

Input

Input consists of one line with one integer $x_0$, the initial term of the sequence, where $0\le x_0\le 100000$.

Output

Output consists of one or more lines, where the $i$th line contains the integer $x_i$, for $i\ge 0$.

2

2
1

3

3
10
5
16
8
4
2
1

19

19
58
29
88
44
22
11
34
17
52
26
13
40
20
10
5
16
8
4
2
1

25

25
76
38
19
58
29
88
44
22
11
34
17
52
26
13
40
20
10
5
16
8
4
2
1