|
Билл пытается компактно представить последовательность заглавных латинских букв от 'A' до 'Z', с учетом
повторяющихся последовательностей в ней. Например, возможный способ представить
последовательность AAAAAAAAAABABABCCD - есть 10(A)2(BA)B2(C)D. Билл ввел
формальное понятие упакованной последовательности так:
Последовательность, содержащая один символ из диапазона 'A'..'Z' считается
упакованной последовательностью. Ее распаковка возвращает тот же символ.
Если S и Q - упакованные последовательности, то SQ - также упакованная
последовательность. Причем, если результатом распаковки S является S', а Q - Q',
то SQ распаковывается в S'Q'.
Если S - упакованная последовательность, то X(S) - также упакованная
последовательность, где X - десятичное целое число, большее 1. Если S
распаковывается в S', то X(S) распаковывается в S', повторенную X раз.
Согласно этому определению легко распаковать любую запакованную
последовательность. На Билл более заинтересован в обратной операции. Он хочет
запаковать данную последовательность так, чтобы результирующая запакованная
последовательность содержала как можно меньше символов (включая цифры и
скобки).
Input
Входные данные содержат одну строку, состоящую не менее, чем
из одного и не более чем из 100 символов в диапазоне 'A'..'Z'.
Output
Запишите в выходной файл одно число - длину кратчайшего из вариантов
запаковки исходной последовательности.
Samples
| Input | Output |
|---|
| AAAAAAAAAABABABCCD | 12 |
| NEERCYESYESYESNEERCYESYESYES | 14 |
| 
