Matcom Online Grader

Pepe ha estado usando últimamente el compactador que Fito creó ( TextCompact ). El algoritmo inventado por Fito aprovecha al máximo los patrones que se repiten en un texto . Si su algoritmo se encuentra la cadena 'abcabcabc ' entonces lo representa como ‘ (abc)3 ’. Si TextCompact se encuentra el texto ' axyxyxyxyb ’, lo reescribe como ‘ a(xy)4b' y adicionalmente, patrones anidados pueden ser aprovechados como el siguiente ejemplo:

Luego de pensarlo un poco, Pepe ha decidido contratarte para que implementes desde cero el algoritmo de compresión de Fito. En otras palabras, dado una cadena S, usted debe representarla con la menor cantidad de caracteres, incluyendo los paréntesis y los dígitos.

Input

Línea 1 : Una cadena $S$ de longitud a lo sumo 1000 ($|S|$, conteniendo solamente letras en minúscula del alfabeto inglés $(a, b, …, z)$.

Output

Línea 1 : El resultado de comprimir $S$. Note que la solución no necesariamente es única.

Sample test(s)

Hints

Hint

Note que TextCompact produce el menor texto posible (incluyendo los paréntesis y dígitos). Para el ejemplo, el texto original contiene 16 caracteres y el resultado de comprimirlo 12.