Write down any number on a piece of paper, for example

886328712442992

Count up the number of even and odd digits, and the total number of digits. As such, the sample number given above contains 10 even digits and 5 odd digit, or 15 digits in total. String the digits of these three numbers (10, 5 and 15) together to make a new number

10515

Write this number underneath the previous number on the piece of paper. Now perform the same operation starting from the new number. The number 10515 has one even number and 4 odd numbers, or 5 numbers in total. Concatenate the digits of these three numbers to get the new number

145

The number 145 contains one even digit and 2 odd digits, or 3 digits in total. If you string together these three numbers, you'll end up with the number

123

Now, if you would repeat the same procedure starting from the number 123, you again get the number 123.

Go ahead and try the procedure for yourself starting from any number that you like. You'll notice that you will always end up with the same magic number.

Input

A number $$n \in \mathbb{N}$$.

Output

Apply the above procedure to the number $$n$$ and output all intermediate results on a separate line. The procedure ends when the number 123 is reached.

Example

Input:

886328712442992

Output:

10515
145
123