A Cure for the Common Code

You send coded messages to the other fighters in the resistance. Each message is a string of lowercase letters that you scratch onto a monument in the middle of the night.

You write the messages by hand, so a longer message means more time in the open and a greater chance of being caught by the empire. To keep messages short you write them with an encoding that marks a repeated substring with digits and parentheses, and you use that notation only when it is shorter than writing the substring out.

An encoded message is a run of parts read from left to right. Decode each part and join the results in order, and you get the original string. A part has one of these two forms.

• A single lowercase letter, which decodes to itself.
• A repeat count $k$ with $k \ge 2$, written in decimal with no leading zeros, followed by the thing it repeats. When the repeated thing is a single letter, the letter goes right after the count with no parentheses. Otherwise an encoded message goes inside parentheses.

The length of an encoding is the number of characters you actually scratch. A letter, a digit and a parenthesis each count as 1.

The 10 character string abcbcbcbca is written as the 7 character string a4(bc)a. A repeat can hold another repeat, so the 20 character string abbbcdcdcdabbbcdcdcd is written as the 11 character string 2(a3b3(cd)).

Given a string, find the length of its shortest encoding.

Each line of input holds one string of lowercase letters whose length is at most 500. A line holding a single 0 ends the input, and that line is not a string to encode.

For each string, in the order it was given, print one line of the form Case x: y. Here $x$ is the number of the string counting from 1, and $y$ is the smallest number of characters an encoding of that string needs.