伊万想给他的朋友写一封信。该字母是由小写拉丁字母组成的字符串 s。
不幸的是,当伊万开始写这封信时,他意识到这封信很长,写整封信可能需要非常长的时间。所以他想写字符串 s 的压缩版本而不是字符串本身。
字符串 s 的压缩版本是字符串 c1、s1、c2、s2、...、ck、sk 的序列,其中 ci 是数字 ai 的十进制表示形式(不带任何前导零),si 是由小写拉丁字母组成的字符串。如果 Ivan 将字符串 s1 精确写入 a1 次,然后将字符串 s2 精确写入 a2 次,依此类推,结果将是字符串 s。
压缩版本的长度为 |c1| + |s1| + |c2| + |s2|... |ck| + |sk|。在所有压缩版本中,Ivan 希望选择一个长度尽可能最小的版本。帮助 Ivan 确定可能的最小长度。
输入
输入的唯一一行包含一个由小写拉丁字母组成的字符串 s (1 ≤ |s| ≤ 8000)。
输出
输出一个整数 — s 的压缩版本的最小可能长度。
示例
输入 #1
aaaaaaaaaa
输出 #1
3
输入 #2
abcab
输出 #2
6
输入 #3
cczabababab
输出 #3
7
注意
在第一个示例中,Ivan 将选择此压缩版本:c1 是 10,s1 是 a。
在第二个示例中,Ivan 将选择此压缩版本:c1 为 1,s1 为 abcab。
在第三个示例中,Ivan 将选择此压缩版本:c1 为 2,s1 为 c,c2 为 1,s2 为 z,c3 为 4,s3 为 ab。