String operations

For a given string, perform the following operation: append to it the same string written in the reverse order. With the resulting string we perform the same operation and so on.

According to the result string, you need to determine the initial one, as well as how many times the specified operation is performed (the number of operations should be minimal).

Input

One line formed as a result of several operations. The string length does not exceed 10^6.

Output

In the first line print the starting string. In the second line print the number of operations.

Examples