Folding

Bill is trying to compactly represent sequences of capital alphabetic characters from $A$ to $Z$ by folding repeating subsequences inside them. For example, one way to represent the sequence AAAAAAAAAABABABCCD is 10(A)2(BA)B2(C)D. He formally defines folded sequences of characters along with the unfolding transformation for them in the following way:

- A sequence that contains a single character from $A$ to $Z$ is considered to be a folded sequence. Unfolding this sequence produces the same single character itself.

- If $S$ and $Q$ are folded sequences, then $SQ$ is also a folded sequence. If $S$ unfolds to S' and $Q$ unfolds to Q', then $SQ$ unfolds to S'Q'.

- If $S$ is a folded sequence, then $X(S)$ is also a folded sequence, where $X$ is a decimal representation of an integer number greater than $1$. If $S$ unfolds to S', then $X(S)$ unfolds to S' repeated $X$ times.

According to this definition, it is easy to unfold any given folded sequence. However, Bill is much more interested in the reverse transformation. He wants to fold the given sequence in such a way that the resulting folded sequence contains the fewest possible number of characters.