문자열 접기

Bill은 'A'부터 'Z'까지의 대문자로만 이루어진 문자열에서 반복되는 부분을 접어 더 짧게 표현하려고 한다. 예를 들어 문자열 AAAAAAAAAABABABCCD는 10(A)2(BA)B2(C)D로 표현할 수 있다.

접힌 문자열(folded sequence)과 이를 펼치는(unfolding) 규칙은 다음과 같이 정의된다.

• 'A'부터 'Z'까지의 문자 하나로 이루어진 문자열은 접힌 문자열이다. 이 문자열을 펼치면 그 한 글자 자신이 된다.
• $S$와 $Q$가 접힌 문자열이면 $SQ$도 접힌 문자열이다. $S$가 $S'$로 펼쳐지고 $Q$가 $Q'$로 펼쳐지면, $SQ$는 $S'Q'$로 펼쳐진다.
• $S$가 접힌 문자열이면 $X(S)$도 접힌 문자열이며, 여기서 $X$는 1보다 큰 정수의 십진 표기이다. $S$가 $S'$로 펼쳐지면 $X(S)$는 $S'$를 $X$번 반복한 문자열로 펼쳐진다.

주어진 문자열을 접어서 만들 수 있는 접힌 문자열 중, 글자 수가 가장 적은 것의 글자 수를 구하여라.

'A'부터 'Z'까지의 대문자로 이루어진 문자열 한 줄이 주어진다. 문자열의 길이는 1 이상 100 이하이다.

입력 문자열로 펼쳐지는 접힌 문자열 중, 글자 수가 가장 적은 것의 글자 수를 정수 하나로 출력한다.