License plates

Input

A single line contains a numeric string $s$ (1 \leq |s| \leq 1\,000\,000), where $|s|$ is the length of the string. Note that the string can start with $0$.

Output

Output the solution to the problem on a single line.

Examples

Note

In the first example, you can transform $23$ into $00$ using $5$ operations, or into $27$ using $4$ operations, which is more efficient.

In the second example, you can change $228$ to $279$ with $6$ operations, or to $018$ with $3$ operations, which is more efficient.

In the third example, $0234$ is already divisible by $9$, so it is the solution.

String $a$ is lexicographically smaller than string $b$ if one of the following conditions is met:

• $a$ is a prefix of $b$, but a \neq b;

• at the first position where $a$ and $b$ differ, the character in $a$ comes earlier in the alphabet than the corresponding character in $b$.