题目描述

对任意一个自然数 $N_0$，先将其各位数字相加求和，再将和乘以 $3$ 后加 $1$，得到新自然数 $N_1$；重复此操作可产生 $N_2, N_3, \dots$。多次操作后，结果会固定不变，掉入数字“陷阱”。本题要求输出输入自然数掉入陷阱的过程。

（术语说明：各位数字相加是指将自然数的十进制表示中的每一位数字相加，例如 $123$ 的各位数字之和为 $1+2+3=6$。）

输入格式

在一行内输入一个自然数 $N_0$（$0 \le N_0 < 30000$）。

输出格式

逐行输出掉入陷阱的步骤。第 $i$ 行格式为 i:N_i（$i \ge 1$）。当某一步结果 $N_k$ 与上一步 $N_{k-1}$ 相同时，停止输出。

样例输入

5

样例输出

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

数据范围

$0 \le N_0 < 30000$