Le mucche giocano a un gioco con i numeri. Partono da un numero, per esempio 6593. Ne estraggono le cifre (per esempio 6, 5, 9, 3) e le moltiplicano tra loro per ottenere un prodotto (in questo caso, $6 x 5 x 9 x 3 = 810$). Ripetono l’operazione (per esempio $8 x 1 x 0$) ottenendo 0, un numero di una sola cifra.

Aiuta le mucche a giocare. Leggi un numero e mostra i passaggi per ottenere una sola cifra.

Input

Un intero iniziale $N$ ($10 \le N \le 2{,}000{,}000{,}000$).

Output

Una sola riga con interi: il numero iniziale e i numeri successivi ottenuti dal calcolo, fino a ottenere un numero di una sola cifra.

Esempi

Input 1

98886

Output 1

98886 27648 2688 768 336 54 20 0

Autore del problema: Russ Cox