Білл намагається компактно подати послідовности прописних символів від \textbf{A} до \textbf{Z} при допомозі пакування повторюваних підпослідовностей всередині них. Наприклад, один зі способфв подати послідовність \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}(\textbf{S}) - також упакована послідоність, де \textbf{X}- десяткове подання цілого числа, більшого \textbf{1}. Якщо \textbf{S} розпаковується в \textbf{S′}, то \textbf{X}(\textbf{S}) розпаковується в \textbf{S′}, повторену \textbf{X} разів. \end{itemize} Дотримуючись цих правил, легко розспаковати довільну задану упаковану послідовність. Проте Біллу більш цікавий зворотній перехід. Він хоче упакувати послідовність так, щоб результуюча стиснена послідовність містила найменше можливе число символів. \InputFile У першому рядку знаходиться послідовність символів від \textbf{A} до \textbf{Z}. Довжина заданої послідовності від \textbf{1} до \textbf{100}. \OutputFile У єдиному рядку виводиться упакована послідовність найменшої довжини, яка розпаковується у задану послідовність. Якщо таких послідовностей декілька, можна вивести довільну.