Module: Patterns in Dynamic Programming

Problem

Chloe wants to write a letter to her friend. Letter - string s, consisting of lowercase Latin letters.
Unfortunately, as soon as Chloe started writing the letter, she realized that it was too long, and it would take a very long time to write it in its entirety. So she wants to write a compressed version of the string s instead of the string itself.

A compressed version of the string s — the sequence of strings c₁, s₁, c₂, s₂,  ..., c_k, s_k, where c_i — decimal representation of a_i (without leading zeros), and s_i — some string of lowercase Latin letters. If Chloe writes the string s₁ exactly a₁ times, then s₂ exactly a₂ times, and so on , it will produce the string s.
The length of the compressed version is |c₁| + |s₁| + |c₂| +  |s₂|... |c_k| + |s_k|. Among all the compressed versions, Chloe wants to choose the one with the shortest length. Help Chloe find the shortest possible length.

Input:
The single line of the input contains a string s consisting of lowercase Latin letters (1 ≤ |s| ≤ 5000).

Output:
Print a single integer — the minimum length of the compressed version of the string s.

Examples:
 

Input	Output
aaaaaaaaaa	3
abcab	6
cczabababab	7

Explanations:
In the first example, Chloe will select the following version: c₁ — 10, s₁ — a.
In the second example, Chloe will choose the following version: c₁ — 1, s₁ — abcab.
In the third example, Chloe will choose the following version: c₁ — 2, s₁ — c, c₂ — 1, s₂ — z, c₃ — 4, s₃ — ab.