Машина Мак-Каллоха
Однажды инспектор Крейг навестил своего старого приятеля Нормана Мак-Каллоха, которого он не встречал уже несколько лет. Они подружились, еще будучи студентами Оксфордского университета, и Крейг всегда с большой теплотой вспоминал те дни и своего друга - отличного парня, правда, немного чудаковатого, который постоянно выдумывал всякого рода технические курьезы. И хотя наш рассказ относится ко времени, когда современные ЭВМ еще не были изобретены, Мак-Каллоху уже в ту пору удалось сконструировать нечто вроде механического счетно-решающего устройства, но, конечно, по нынешним меркам, весьма примитивного.
Эта машина принимает на вход некоторое число 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.