The cows play a game with numbers. They start with some number, say, 6593. They extract the digits (e.g., 6, 5, 9, 3) and multiply them together to form a product (in this case, $6 x 5 x 9 x 3 = 810$). They do this again (e.g., $8 x 1 x 0$) to get 0, a one digit number.
Help the cows play their game. Read in a number and show the steps to get to a single digit.
Input
A starting integer $N$ ($10 \le N \le 2{,}000{,}000{,}000$).
Output
A single line with integers that are the starting number and the successive numbers from the calculation until a single digit is obtained.
Examples
Input 1
98886Output 1
98886 27648 2688 768 336 54 20 0Problem credits: Russ Cox