Біл хоче скоротити запис послідовності, яка складається з великих латинських букв. Для цього він може згорнути її повторювані підпослідовності. Наприклад, послідовність \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 У вихідний файл виведіть один рядок, який містить найменшу послідовність розгортка якої дає рядок, заданий у вхідному файлі. Якщо відповідей декілька - виведіть довільну з них.