Assignment

Write a program that asks the user for a positive integer, and then prints the complete Collatz sequence (also called the 3n + 1 sequence), starting from that number and ending at 1.

What is the Collatz sequence?

The Collatz sequence is a sequence of numbers where each next number is calculated according to these two rules:

  1. Is the number even? Divide it by 2.
  2. Is the number odd? Multiply it by 3 and add 1.

Repeat these steps over and over.

The Collatz Conjecture states that you will always eventually reach the number 1, no matter which positive integer you start with.

Below are some examples:

Starting number Collatz sequence Why?
6 6, 3, 10, 5, 16, 8, 4, 2, 1 6 / 2 = 3
3 × 3 + 1 = 10
10 / 2 = 5
...
11 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1 11 × 3 + 1 = 34
34 / 2 = 17
...
19 19, 58, 29, 88, 44, 22, 11, ... , 2, 1 19 × 3 + 1 = 58
58 / 2 = 29
...

(PS: While this hypothesis has not been mathematically proven, no one has yet found a positive integer that does not end at 1.)




Examples

Example 1

Input

6

Output

Collatz sequence:
6
3
10
5
16
8
4
2
1
Example 2

Input

11

Output

Collatz sequence:
11
34
17
52
26
13
40
20
10
5
16
8
4
2
1
Example 3

Input

19

Output

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