Машина Мак-Каллоха
Одного разу інспектор Крейг відвідав свого старого приятеля Нормана Мак-Каллоха, якого він не зустрічав уже декілька років. Вони подружились, ще будучи студентами Оксфордського університету, і Крейг завжди з великою теплотою згадував ті дни і свого друга - гарного хлопця, правда, трішки чудаковатого, який постійно видумував усілякі технічні курйози. І хоча наша розповідь відноситься до часів, коли сучасні ЕОМ ще не були винайдені, Мак-Каллоху вже у той час вдалось сконструювати дещо схоже на механічний рахувально-розв'язуючий пристрій, але, звичайно, по нинішнім міркам, досить примітивний.
Ця машина приймає на вхід деяке число X і, якщо воно є допустимим, то породжує відповідне йому число Y, діючи за строго визначеними законами. Під числом тут розуміється довільне ціле додатнє число, яке записується звичним способом у вигляді деякої послідовності цифр 0, 1, 2, 3, 4, 5, 6, 7, 8, 9.
Для довільного (можливо навіть порожнього) числа X число 2X (тут і далі під N M розуміється конкатенація записів чисел N та M ) є допустимим числом, причому число 2X породжує число X.
Для довільного допустимого числа X, число 3X також є допустимим. При цьому, якщо число X породжує число Y, то число 3X породжує ассоціат числа Y, тобто число Y 2Y.
Для довільного допустимого числа X, число 4X також є допустимим. При цьому, якщо число X породжує число Y, то число 3X породжує обернення числа Y (тобто число, яке отримується якщо записати послідовно усі цифри числа Y у зворотньому порядку, будемо позначати його Y).
Для довільного допустимого числа X, число 5X також є допустимим. При цьому, якщо число X породжує число Y, то число 5X породжує повторення числа Y, тобто число Y Y.
Для довільного допустимого числа X, число 6X також є допустимим. При цьому, якщо число X породжує число Y, то число 6X породжує число 2Y.
Для довільного допустимого числа X, число 7X також є допустимим. При цьому, якщо число X породжує число Y, то і число 7X породжує число Y.
Для довільного допустимого числа X, число 8X також є допустимим. При цьому, якщо число X породжує число Y, то число 8X породжує число Y без останньої цифри, якщо у числі Y є хоча б одна цифра, чи порожнє число, якщо Y було порожнім.
Потрібно за заданим числом X визначити число Y, яке по ньому породжує машина Мак-Каллоха.
Вхідні дані
У єдиному рядку вхідного файлу задається одне ціле число X, яке містить не більше 10^5 цифр.
Вихідні дані
У єдиний рядок вихідного файлу необхідно вивести число Y, яке породжується числом X у машині Мак-Каллоха. Якщо число X не є допустимим, вивести Invalid input. Гарантується, що довжина породжуваного числа Y не перевищує 10^6.