Description

Given a string consisting of lowercase letters, we can compress its repeated information using a simple method. The compressed string may (but does not have to) contain uppercase letters $\texttt{R}$ and $\texttt{M}$ in addition to lowercase letters, where $\texttt{M}$ marks the start of a repeated segment, and $\texttt{R}$ repeats the decompressed result starting from the previous $\texttt{M}$ (if there is no $\texttt{M}$ to the left of the current position, start from the beginning of the string), which is called the buffer string.

$\texttt{bcdcdcdcd}$ can be compressed as $\texttt{bMcdRR}$. The decompression process is shown below:

Input Format

The input contains a single line with the string to compress, consisting only of lowercase letters, of length $n$.

Output Format

Output a single line: the minimum possible length of the compressed string.

aaaaaaa

5

bcdcdcdcdxcdcdcdcd

12

Hint

In the first example, an answer is $\texttt{aaaRa}$. In the second example, an answer is $\texttt{bMcdRRxMcdRR}$.

Constraints

• For $50\%$ of the testdata, $1\le n \le 20$.
• For $100\%$ of the testdata, $1\le n \le 50$.

Translated by ChatGPT 5