eolymp
bolt
Try our new interface for solving problems
Problems

String operations

String operations

Time limit 1 second
Memory limit 128 MiB

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 data

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

Output data

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

Examples

Input example #1
ABBAABBAABBAABBA
Output example #1
AB
3
Source 2019 All-Ukrainian Olympiad, Zhitomyr region, ІІ stage