Migrated from Lutece 1039 Fabricate equation

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

Given an integer $Y$, you need to find the minimal integer $K$ so that there exists a $X$ satisfying $X - Y = Z (Z \geq 0)$ and the number of different digit between $X$ and $Z$ is $K$ under decimal system.

For example: $Y = 1$, you can find a $X = 100$ so that $Z =99$ and $K$ is $3$ due to $1 \neq 0$ and $0 \neq 9$. But for minimization, we should let $X = 1$ so that $Z = 0$ and $K$ can just be $1$.

Input

Only one integer $Y (0 \leq Y \leq 10^{18}).$

Output

The minimal $K$.

Samples

1

1

191

2

Resources

The 13th UESTC Programming Contest Preliminary