Shortest Folded Representation

Given a string S, find its shortest folded representation. The folded representation is defined as follows:

1. A string can be seen as its own folded form. That is, S = S.
2. If you concatenate S exactly X times, then the folded representation is written as X(S), which stands for S repeated X times. For example, 3(A) represents AAA.
3. If A can be folded as A' and B as B', then the concatenation AB can be folded as A'B'. For example, since 3(A)=AAA and 2(B)=BB, we have 3(A)C2(B)=AAACBB, and 2(3(A)C)2(B)=AAACAAACBB.

Given a string, you are to output its shortest folded representation. For instance, for the input string:

AAAAAAAAAABABABCCD

the shortest folded representation is:

9(A)3(AB)CCD

Note: If there are multiple folded representations with the same length, any one of them is accepted.

inputFormat

The input consists of a single line containing the string S. The string consists only of uppercase letters.

outputFormat

Output the shortest folded representation of the given string S.

sample

AAAAAAAAAABABABCCD

9(A)3(AB)CCD