Avtomobil nömrələri

Kazak Vus və Ledi avtomobillə səyahət edərkən bir oyun oynamağı çox sevirlər. Onlar avtomobilin nömrəsindəki rəqəmlərə baxaraq, bu rəqəmi ən az əməliyyatla 9-a bölünən etmək istəyirlər.

Bir əməliyyat, hər hansı bir rəqəmə bir vahid əlavə etmək və ya çıxarmaqdan ibarətdir. Rəqəmlər həmişə 0-dan 9-a qədər olmalıdır, yəni 0-dan çıxarmaq və ya 9-a əlavə etmək mümkün deyil.

Dostlar bu oyundan tez bezdilər və onu daha da çətinləşdirmək qərarına gəldilər. İndi onlar bütün mümkün həllər arasında leksikoqrafik olaraq ən kiçiyini tapmalıdırlar.

Potokolyandiyada avtomobil nömrələri olduqca böyükdür, buna görə də bu oyunu oynamaq çətindir. Buna görə də, sizdən onlar üçün bu oyunu oynayacaq bir proqram yazmağınızı xahiş edirlər.

Giriş formatı

Yeganə sətir rəqəmsal sətir s (1 ≤ |s| ≤ 1 000 000) ehtiva edir, burada |s| sətirin uzunluğunu göstərir. Qeyd edək ki, sətir «0» ilə başlaya bilər.

Çıxış formatı

Yeganə sətirdə məsələnin cavabını çıxarın.

Qeyd

Birinci nümunədə 23-dən 00-ı 5 əməliyyatla, ya da 27-ni 4 əməliyyatla etmək olar ki, bu da daha sərfəlidir.

İkinci nümunədə 228-dən 279-u 6 əməliyyatla, ya da 018-i 3 əməliyyatla etmək olar ki, bu da daha sərfəlidir.

Üçüncü nümunədə 0234 dərhal 9-a bölünür, buna görə də cavabdır.

Sətir a leksikoqrafik olaraq sətir b-dən kiçikdir, əgər və yalnız əgər aşağıdakı iki şərtdən biri yerinə yetirilirsə:

• a — b-nin prefiksidir, amma a ≠ b;

• a və b fərqli olan ilk mövqedə, a sətirindəki hərf əlifbada b-dəki müvafiq hərfdən əvvəl gəlir.