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.

They 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 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 '*'.

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