### 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.

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湖南大学校赛