The Number Trap

Problem Description

For any natural number $N_0$, first add up its digits to get a sum, then multiply that sum by $3$ and add $1$ to obtain a new natural number $N_1$; repeating this operation produces $N_2, N_3, \dots$. After enough steps the result stops changing and falls into a numerical "trap". This problem asks you to output the whole process of the input number falling into the trap.

(Terminology: adding up the digits means summing every digit in the decimal representation of the number — for example, the digit sum of $123$ is $1+2+3=6$.)

Input Format

One line containing a natural number $N_0$ ($0 \le N_0 < 30000$).

Output Format

Output the steps of falling into the trap, one step per line. The $i$-th line has the format i:N_i ($i \ge 1$). Stop outputting as soon as some step $N_k$ equals the previous step $N_{k-1}$.

Sample Input

5

Sample Output

1:16
2:22
3:13
4:13