CF825F.String Compression

Ivan wants to write a letter to his friend. The letter is a string s consisting of lowercase Latin letters.

Unfortunately, when Ivan started writing the letter, he realised that it is very long and writing the whole letter may take extremely long time. So he wants to write the compressed version of string s instead of the string itself.

The compressed version of string s is a sequence of strings _c_1, _s_1, _c_2, _s_2, ..., c__k, s__k, where c__i is the decimal representation of number a__i (without any leading zeroes) and s__i is some string consisting of lowercase Latin letters. If Ivan writes string _s_1 exactly _a_1 times, then string _s_2 exactly _a_2 times, and so on, the result will be string s.

The length of a compressed version is |_c_1| + |_s_1| + |_c_2| + |_s_2|... |c__k| + |s__k|. Among all compressed versions Ivan wants to choose a version such that its length is minimum possible. Help Ivan to determine minimum possible length.

伊万想给他的朋友写一封信。这封信是一个由小写拉丁字母组成的字符串 $ s $。

不幸的是，当伊万开始写这封信时，他意识到信件非常长，完整写出整个字符串将耗费极长的时间。因此，他希望改写字符串 $ s $ 的压缩版本，而非原始字符串本身。

字符串 $ s $ 的压缩版本是一个字符串序列 $ c_1,,s_1,,c_2,,s_2,,\dots,,c_k,,s_k $，其中 $ c_i $ 是某个整数 $ a_i $ 的十进制表示（不含前导零），而 $ s_i $ 是一个由小写拉丁字母组成的字符串。若伊万将字符串 $ s_1 $ 恰好重复 $ a_1 $ 次、字符串 $ s_2 $ 恰好重复 $ a_2 $ 次，依此类推，则最终拼接得到的字符串即为 $ s $。

该压缩版本的长度定义为 $ |c_1| + |s_1| + |c_2| + |s_2| + \dots + |c_k| + |s_k| $。在所有可能的压缩版本中，伊万希望选择长度最小的一个。请帮助伊万确定该最小可能长度。

The only line of input contains one string s consisting of lowercase Latin letters (1 ≤ |s| ≤ 8000).

输入仅包含一行，其中有一个由小写拉丁字母组成的字符串 $s$（$1 \le |s| \le 8000$）。

Output one integer number — the minimum possible length of a compressed version of s.

输出一个整数——字符串 $s$ 的压缩版本的最小可能长度。

In the first example Ivan will choose this compressed version: _c_1 is 10, _s_1 is a.

In the second example Ivan will choose this compressed version: _c_1 is 1, _s_1 is abcab.

In the third example Ivan will choose this compressed version: _c_1 is 2, _s_1 is c, _c_2 is 1, _s_2 is z, _c_3 is 4, _s_3 is ab.

在第一个例子中，伊万将选择以下压缩版本：$c_1$ 为 10，$s_1$ 为 a。

在第二个例子中，伊万将选择以下压缩版本：$c_1$ 为 1，$s_1$ 为 abcab。

在第三个例子中，伊万将选择以下压缩版本：$c_1$ 为 2，$s_1$ 为 c；$c_2$ 为 1，$s_2$ 为 z；$c_3$ 为 4，$s_3$ 为 ab。