007 - おみくじ

アイヅ赤ベコ神社には、変わったおみくじがあります。おみくじには、２桁以上の数が書いてあります。ただし、この神社では0 は縁起の悪い数字とされているので、各桁は1 から9 までの数字です。

このおみくじから次のようにして、願い事が何年後にかなうか占うことができます。おみくじに書かれた数を１か所以上で切ります。切り分けられた数のうち最 大と最小のものの差が、願い事がかなうまでにかかる年数になります。あなたが数をどのように切り分けるかによって、かなうまでの年数が変わります。たとえ ば、おみくじに書かれた数が11121314 のとき、これを1,11,21,3,14 のように切り分ければ21-1=20 年になります。11,12,13,14 のように切り分ければ14-11=3 年になります。何も考えずに切った場合、どれだけ早くかなえられるかは運次第ですが、運に頼らずに願い事がかなうまでの最小の年数をプログラムで求めるこ ともできます。

おみくじに書かれている数が与えられたとき、願い事がかなうまでの最小の年数を求めるプログラムを作成せよ。

Input

入力は以下の形式で与えられる。

n

１行に正の整数nが与えられる。ただし、nの各桁は1から9の数字からなり、桁数は2以上100,000以下である。

Output

願い事がかなうまでの最小の年数を１行に出力する。

Sample Input 1

11121314

Sample Output 1

3

Sample Input 2

123125129

Sample Output 2

6

Sample Input 3

119138

Sample Output 3

5