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 below 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

Schrijf een willekeurig getal op een blaadje papier, bijvoorbeeld

886328712442992

Tel het aantal even en oneven cijfers in dit getal, alsook het totaal aantal cijfers van het getal. Zo bestaat bovenstaand voorbeeldgetal uit 10 even cijfers en 5 oneven cijfers, in totaal dus 15 cijfers. Schrijf nu de cijfers van deze drie getallen (10, 5 en 15) achter elkaar uit, dan krijg je een nieuw getal

10515

Schrijf dit getal onder het eerste getal op het blaadje papier. Daarna herhaal je dezelfde procedure met dit nieuwe getal. Het getal 10515 bevat één even cijfer en 4 oneven cijfers, in totaal dus 5 cijfers. Plak de cijfers van deze drie getallen aan elkaar en bekom zo het nieuwe getal

145

Het getal 145 bestaat uit één even cijfer en 2 oneven cijfers, in totaal dus 3 cijfers. Als je deze drie getallen achter elkaar schrijft, dan bekomen je het getal

123

Als je nu dezelfde procedure zouden toepassen op het getal 123, dan kom je terug uit bij het getal 123. Probeer de procedure gerust eens uit op een zelfgekozen getal. Je zal merken dat je finaal altijd uitkomt bij hetzelfde magische getal.

Invoer

Een getal $n \in \mathbb{N}$.

Uitvoer

Pas de hierboven omschreven procedure toe op het getal $n$ en schrijf alle tussenresultaten uit op een afzonderlijke regel. De procedure eindigt als het getal 123 bereikt wordt.

Voorbeeld

Invoer:

886328712442992

Uitvoer:

10515
145
123