최소 길이 반복 인코딩

저항군 동료에게 암호문을 전한다. 암호문은 소문자로만 이루어진 문자열이고, 한밤중에 기념비에 몰래 새긴다.

손으로 새기다 보니 문자열이 길수록 새기는 동안 제국에 붙잡힐 위험이 커진다. 그래서 반복되는 부분 문자열을 숫자와 괄호로 표시하는 인코딩을 쓰기로 한다. 그대로 쓰는 것보다 짧아질 때만 이 표기를 쓴다.

인코딩된 암호문은 왼쪽부터 차례로 읽는 조각의 나열이다. 각 조각을 해독한 결과를 순서대로 이어 붙이면 원래 문자열이 된다. 조각은 다음 두 형태 중 하나다.

• 소문자 한 글자. 그 글자 자신으로 해독된다.
• 반복 횟수 $k$ ($k \ge 2$, 앞에 0을 붙이지 않은 10진수)와 반복할 대상. 반복할 대상이 한 글자면 괄호 없이 횟수 바로 뒤에 그 글자를 쓴다. 그렇지 않으면 인코딩된 암호문을 괄호로 감싸서 쓴다.

인코딩의 길이는 실제로 새기는 문자의 개수다. 글자, 숫자, 괄호는 각각 하나를 1로 센다.

10글자인 abcbcbcbca는 7글자인 a4(bc)a로 쓴다. 반복 안에 반복을 넣을 수 있으므로, 20글자인 abbbcdcdcdabbbcdcdcd는 11글자인 2(a3b3(cd))로 쓴다.

문자열이 주어지면 가장 짧은 인코딩의 길이를 구한다.

입력의 각 줄에는 길이가 500 이하인 소문자 문자열이 하나씩 주어진다. 0 하나만 있는 줄이 나오면 입력이 끝나고, 그 줄은 인코딩할 문자열이 아니다.

각 문자열마다 주어진 순서대로 한 줄씩 Case x: y 형식으로 출력한다. $x$는 1부터 세는 문자열의 번호이고, $y$는 그 문자열을 인코딩하는 데 필요한 문자의 최소 개수다.