Козак Вус та Ледi, їдучи автомобiлем, обожнюють грати в одну гру. Вони дивляться на число, записане на номерi автомобiля, та хочуть зробити, щоб воно дiлилося нацiло на 9 за мiнiмальну кiлькiсть операцiй.

Операцiя — це додати або вiдняти одиницю до будь-якої цифри. Звичайно цифри завжди мають бути вiд 0 до 9. Тобто, не можна вiднiмати вiд 0 та додати до 9.

Друзям ця гра швидко набридла, тому вони вирiшили ускладнити її, доповнивши її ще одним правилом — серед усiх можливих рiшень, потрiбно знайти лексикографiчно мiнiмальний.

В Потоколяндiї автомобiльнi номери досить великi, тому грати в цю гру складно, тому компанiя просить вас написати програму, яка буде грати за них.

Формат вхiдних даних

Єдиний рядок мiстить цифровий рядок s (**1 ≤ |s| ≤ 1 000 000**), де |s| — довжина рядка. Звернiть увагу, що рядок може починатись з «0».

Формат вихiдних даних

В єдиному рядку виведiть вiдповiдь на задачу.

Примiтка

У першому прикладi з 23 можна зробити 00 за 5 операцiй, або 27 за 4 операцiї, що є вигiднiшим.

У другому прикладi з 228 можна зробити 279 за 6 операцiй, або 018 за 3 операцiї, що є вигiднiшим.

У третьому прикладi 0234 одразу нацiло дiлиться на 9, тому i є вiдповiддю.

Рядок a лексикографiчно менший за рядок b, якщо i лише якщо виконується один з двох пунктiв:

• a — префiкс b, але a ≠ b;

• у першiй позицiї, де a та b рiзнi, у рядку a знаходиться буква, яка зустрiчається в алфавiтi ранiше, нiж вiдповiдна буква у b.