McCulloch's Machine
Inspector Craig once paid a visit to his old friend Norman McCulloch, whom he hadn't seen in several years. They had become friends during their time as students at Oxford University. Craig fondly remembered those days and his friend, who was a good-natured but somewhat eccentric individual, always inventing various technical gadgets. Although this story takes place before the invention of modern computers, McCulloch had already built a device resembling a mechanical calculator, albeit primitive by today's standards.
This machine accepts a number X as input and, if valid, produces a corresponding number Y based on specific rules. Here, a number refers to any positive integer, represented as a sequence of digits from 0 to 9.
For any number X (including possibly an empty one), the number 2X (where N M denotes the concatenation of numbers N and M) is valid, and 2X generates the number X.
If X is valid, then 3X is also valid. If X generates Y, then 3X generates the number Y 2Y.
If X is valid, then 4X is also valid. If X generates Y, then 4X generates the reverse of Y (i.e., the digits of Y written in reverse order).
If X is valid, then 5X is also valid. If X generates Y, then 5X generates Y Y.
If X is valid, then 6X is also valid. If X generates Y, then 6X generates 2Y.
If X is valid, then 7X is also valid. If X generates Y, then 7X generates Y.
If X is valid, then 8X is also valid. If X generates Y, then 8X generates Y without its last digit, or an empty number if Y was empty.
Your task is to determine the number Y generated by McCulloch's machine for a given number X.
Input
The input consists of a single line containing an integer X, which has no more than 10^5 digits.
Output
Output a single line containing the number Y generated by the number X using McCulloch's machine. If X is not valid, output Invalid input. It is guaranteed that the length of the generated number Y does not exceed 10^6.