Compressing a String

When a certain pattern repeats inside a string, the repetition can sometimes be used to write the string more shortly. This is called compression. RLE (Run Length Encoding) is one of the simplest compression methods: when the same character appears several times in a row, the character is written once together with its repetition count. For example, abccddd can be represented as abc2d3.

If repeated strings are used instead of repeated characters, RLE can be extended. When a string S appears k consecutive times in the given string, it may be written as k(S). For example, letsgogogo can be compressed as lets3(go), whose length is 9. The length of a compressed expression includes the parentheses and the number of digits needed to write the repetition count k.

Compression may also be nested. For example, nowletsgogogoletsgogogo can be compressed as now2(lets3(go)), and nowletsgogogoletsgogogoandrunrunrun can be compressed as now2(lets3(go))and3(run). In this extended method, character repetitions cannot be written as abc2d3; the equivalent form must use string-repetition notation, such as ab2(c)3(d).

Given a string, find the length of the shortest compressed expression that can represent it. Leaving the string uncompressed is also allowed.

The first line contains a string consisting only of lowercase English letters. The string contains no spaces and has length at most 200.

Print the minimum possible length of a compressed expression. If leaving the string uncompressed is shorter or tied for shortest, print the original length.