String Folding

Interview

Time limit2sMemory limit128 MB

Summary

Find the length of the shortest folded sequence, using repeat counts like 3(AB), that unfolds to the given uppercase string.

Level: Medium6 of 10
Topics: Dynamic programming, String
Solved: No attempts yet

Problem

Bill wants to compactly represent strings of uppercase letters 'A' to 'Z' by folding their repeating parts. For example, the string AAAAAAAAAABABABCCD can be written as 10(A)2(BA)B2(C)D.

A folded sequence and its unfolding are defined as follows.

A string consisting of a single character from 'A' to 'Z' is a folded sequence. Unfolding it yields that same single character.
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 the decimal representation of an integer greater than 1. If $S$ unfolds to $S'$ , then $X(S)$ unfolds to $S'$ repeated $X$ times.

Among all folded sequences that unfold to the given string, find the number of characters in the shortest one.

Input

A single line containing a string of uppercase letters from 'A' to 'Z'. Its length is between 1 and 100, inclusive.

Output

Print a single integer: the number of characters in the shortest folded sequence that unfolds to the input string.

Examples2

Example 1
Input
```
AAAAAAAAAABABABCCD
```
Expected output
```
12
```
Example 2
Input
```
NEERCYESYESYESNEERCYESYESYES
```
Expected output
```
14
```