Однажды инспектор Крейг навестил своего старого приятеля Нормана Мак-Каллоха, которого он не встречал уже несколько лет. Они подружились, еще будучи студентами Оксфордского университета, и Крейг всегда с большой теплотой вспоминал те дни и своего друга - отличного парня, правда, немного чудаковатого, который постоянно выдумывал всякого рода технические курьезы. И хотя наш рассказ относится ко времени, когда современные ЭВМ еще не были изобретены, Мак-Каллоху уже в ту пору удалось сконструировать нечто вроде механического счетно-решающего устройства, но, конечно, по нынешним меркам, весьма примитивного. Эта машина принимает на вход некоторое число \textbf{X} и, если оно является допустимым, то порождает соответствующее ему число \textbf{Y}, действуя по строго определенным законам. Под числом здесь понимается произвольное целое положительное число, которое записывается обычным способом в виде некоторой последовательности цифр \textbf{0}, \textbf{1}, \textbf{2}, \textbf{3}, \textbf{4}, \textbf{5}, \textbf{6}, \textbf{7}, \textbf{8}, \textbf{9}. \begin{enumerate} \item Для любого (возможно даже пустого) числа \textbf{X} число \textbf{2X} (здесь и далее под \textbf{N} \textbf{M} понимается конкатенация записей чисел \textbf{N} и \textbf{M} ) является допустимым числом, причем число \textbf{2X} порождает число \textbf{X}. \item Для любого допустимого числа \textbf{X}, число \textbf{3X} также является допустимым. При этом, если число \textbf{X} порождает число \textbf{Y}, то число \textbf{3X} порождает ассоциат числа \textbf{Y}, т.е. число \textbf{Y 2Y}. \item Для любого допустимого числа \textbf{X}, число \textbf{4X} также является допустимым. При этом, если число \textbf{X} порождает число \textbf{Y}, то число \textbf{3X} порождает обращение числа \textbf{Y} (т.е. число, которое получается если записать последовательно все цифры числа \textbf{Y} в обратном порядке, будем обозначать его \textbf{Y}). \item Для любого допустимого числа \textbf{X}, число \textbf{5X} также является допустимым. При этом, если число \textbf{X} порождает число \textbf{Y}, то число \textbf{5X} порождает повторение числа \textbf{Y}, т.е. число \textbf{Y Y}. \item Для любого допустимого числа \textbf{X}, число \textbf{6X} также является допустимым. При этом, если число \textbf{X} порождает число \textbf{Y}, то число \textbf{6X} порождает число \textbf{2Y}. \item Для любого допустимого числа \textbf{X}, число \textbf{7X} также является допустимым. При этом, если число \textbf{X} порождает число \textbf{Y}, то и число \textbf{7X} порождает число \textbf{Y}. \item Для любого допустимого числа \textbf{X}, число \textbf{8X} также является допустимым. При этом, если число \textbf{X} порождает число \textbf{Y}, то число \textbf{8X} порождает число \textbf{Y} без последней цифры, если в числе \textbf{Y} есть хоть одна цифра, или пустое число, если \textbf{Y} было пустым. \end{enumerate} Требуется по заданному числу \textbf{X} определить число \textbf{Y}, которое по нему порождает машина Мак-Каллоха. \InputFile В единственной строке входного файла задается одно целое число \textbf{X}, содержащее не более \textbf{10^5} цифр. \OutputFile В единственную строку выходного файла необходимо вывести число \textbf{Y}, порождаемое числом \textbf{X} в машине Мак-Каллоха. Если число \textbf{X} не является допустимым, вывести \textbf{Invalid input}. Гарантируется, что длина порождаемого числа \textbf{Y} не превосходит \textbf{10^6}.