Problem Description

If a number is the sum of an integer’s several shifting forms, it is called the Shift Number.
For example, by shifting 123 four times and adding the four numbers together, we get 136653, which is a Shift Number.
However, a shift number may be the sum of more than one integer’s shifting forms. Such as, 45177 is a Shift Number, which could be generated from both 407 and 4107.
123+1230+12300+123000=136653
407+4070+40700=45177
4107+41070=45177
Given a Shift Number x , would you please help us find the least integer which could generate x by shifting.

Input

A shift number x.
Input ends with x=0.

Output

the least integer which could generate x by shifting.

136653
45177
0

123
407

Hint

If you are not familiar with “long long”, you can consult to FAQ.