/**
题目：F. String Compression
链接：http://codeforces.com/problemset/problem/825/F
题意：压缩字符串后求最小长度。
思路：
dp[i]表示前i个字符需要的最小次数。
dp[i] = min(dp[j]+w(j+1,i)); (0<=j<i); [j+1,i]如果存在循环节(自身不算)，那么取最小的循环节x。w = digit((i-j)/x)+x;
否则w = i-j+1; 求一个区间最小循环节：
证明：http://www.cnblogs.com/chenxiwenruo/p/3546457.html
KMP最小循环节、循环周期： 定理：假设S的长度为len，则S存在最小循环节，循环节的长度L为len-next[len]，子串为S[0…len-next[len]-1]。 如果next[len]==0,T = len/L = 1; 说明自身就是循环节。周期为1. （1）如果len%(len - next[len])==0，则表明字符串S可以完全由循环节循环组成，循环周期T=len/L。（这里的len就是从0开始的len位置，kmp也计算了next[len]。） （2）如果不能，说明还需要再添加几个字母才能补全。需要补的个数是循环个数L-len%L=L-(len-L)%L=L-next[len]%L，L=len-next[len]。
*/ #include <cstdio>
#include <cstring>
#include <algorithm>
#include <set>
#include <queue>
#include <iostream>
#include <vector>
using namespace std;
#define ms(x,y) memset(x,y,sizeof x)
const int N = 8e3 + ;
const int INF = 0x3f3f3f3f;
char s[N];
int f[N];
int dp[N];
int w[N][N];///w[i][j]表示[i,j]字符串的价值。
int digit(int x)
{
int cnt = ;
while(x){
cnt++;
x /= ;
}
return cnt;
}
void getFail(char *p,int* f)
{
int m = strlen(p);
f[] = f[] = ;
for(int i = ; i < m; i++){
int j = f[i];
while(j&&p[i]!=p[j]) j = f[j];
f[i+] = (p[i]==p[j])?j+:;
}
}
void solve(char *s)
{
int n = strlen(s);
for(int i = ; i < n; i++) w[i][i] = ;
for(int i = ; i < n; i++){
getFail(s+i,f);
for(int j = i+; j <= n; j++){
int len = j-i;
int d = len-f[j-i];
if(f[j-i]==||len%d!=){
w[i][j-] = len+;
}else
{
w[i][j-] = digit(len/d)+d;
}
}
}
}
int main()
{
while(scanf("%s",s)==)
{
solve(s);
int n = strlen(s);
dp[] = w[][];
for(int i = ; i < n; i++){
dp[i] = w[][i];///整段[0,i]。
for(int j = ; j < i; j++){
dp[i] = min(dp[i],dp[j]+w[j+][i]);
}
}
printf("%d\n",dp[n-]);
} return ;
}