Optimal Compress

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

  In the early year age,the storerage of the computer is very expensive.So when storing message,the worker try to compress the message.Since the storerage is very expensive.The message doesn't exceed 200. 
  compress the message in the following way.
  - adjacent repeats:[S]k
  Which means:S repeated k times(where k is a one-byte integer.Recall that the length of message doesn't exceed 200).
- repeats with gaps:[S]k{S_1}t_1{S_2}t_2...{S_r}t_r, where 1 <= t_i < k, t_i < t_{i+1}
which means: write S for k times, then insert string S_i after the t_i-th occurrence of S.
Note that the message S can be compressed further.
For example:
aaabaaabaaa
Can be compressed into:
[a]9{b}4{b}8 with length 12
and aaa[baaa]2 with length 10
In fact the optimal compress is aaa[baaa]2
aaaaaaaabaaaa
Can be compressed into [a]12{b}8 which is the optimal compress.

Input

  Input consist of multi test case.Each test case is a string conist of lowerletters. And the length doesn't exceed doesn't 200.Input ends with a line contain a singal letter '*'. 

Output

  One integer for each case,the optimal compress string's length. 

Sample Input

aaabaaabaaa
aaaaaaaabaaaa
*

Sample Output

10
8

Hint

 

Source

2010湖南大学校赛