Билл хочет сократить запись последовательности, состоящей из заглавных латинских букв. Для этого он может свернуть ее повторяющиеся подпоследовательности. Например, последовательность \textbf{AAAAAAAAAABABABCCD }может быть записана как \textbf{10(A)2(BA)B2(C)D}. Формальное определение свернутой последовательности и соответствующей ей операции развертки дается следующим образом: \begin{itemize} \item Последовательность, которая содержит единственный символ от '\textbf{A}' до '\textbf{Z}' представляет из себя свернутую последовательность. При развертке такой последовательности получается она сама. \item Если \textbf{S} и \textbf{Q} - свернутые последовательности, то \textbf{SQ} также свернутая последовательность. Если при развертке строки \textbf{S} получается строка \textbf{S'}, а при развертке \textbf{Q} получается \textbf{Q'}, то при развертке \textbf{SQ} получается строка \textbf{S'Q'}. \item Если \textbf{S} - свернутая последовательность, то \textbf{X(S)} также свернутая последовательность, где \textbf{X} это десятичное представление целого числа большего единицы. Если при развертке строки \textbf{S} получается строка \textbf{S'}, то при развертке \textbf{X(S)} получается строка \textbf{S'}, повторенная \textbf{X} раз. \end{itemize} Билл хочет свернуть заданную последовательность таким образом, чтобы результат содержал наименьшее число символов. \InputFile Входной файл содержит непустую строку, состоящую из заглавных латинских букв. Длина строки не превышает \textbf{100} символов. \OutputFile В выходной файл выведите одну строку, содержащую наименьшую последовательность развертка которой даст строку, заданную во входном файле. Если ответов несколько - выведите любой из них.