Number Card Game

Interview

Time limit1sMemory limit128 MB

Summary

For each starting number S, repeatedly replace it with the product of its digits until a single digit appears, printing every value in order.

Level: Easy2 of 10
Topics: Simulation, Implementation, Math, Array
Solved: No attempts yet

Problem

Sitting in the very front row, Sanggun cannot fool around no matter how boring the class is. But today he simply cannot resist, so he decides to play the "number card game" in his notebook.

The number card game works as follows. First, choose a natural number $S$ . Then multiply all of its digits together to form a new number. Repeat this process until the result becomes a single-digit number.

For example, starting from $95$ gives $9 \times 5 = 45$ . Since $45$ still has two digits, we get $4 \times 5 = 20$ , and then $2 \times 0 = 0$ . Because $0$ is a single digit, the game ends.

Likewise, starting from $396$ proceeds as follows and ends at $2$ .

$3 \times 9 \times 6 = 162$

$1 \times 6 \times 2 = 12$

$1 \times 2 = 2$

Given a natural number $S$ , write a program that prints the process of the number card game.

Input

The input consists of several test cases. Each test case is a single starting value $S$ ( $1 \le S \le 100000$ ). $S$ does not start with $0$ . The last line of the input contains a single $0$ , which must not be processed.

Output

For each nonzero input, print on one line all the numbers that appear until the game ends, separated by single spaces. The first number is the given input value, and the last number is a single digit.

Examples1

Example 1

Input

Expected output

95 45 20 0
396 162 12 2
28 16 6
4
40 0