Cho một xâu ~s~, ta gọi một phép nén xâu ~s~ là việc thực hiện các thao tác sau:

• Tìm xâu ~t~ thỏa mãn có thể tạo ra ~s~ bằng cách lặp lại ~t~ một số lần

• Tìm số ~c~ thỏa mãn để tạo ra xâu ~s~ cần viết liên tiếp ~c~ lần xâu ~t~

• Khi đó, xâu ~p=c+t~ là xâu nén của ~s~

Ví dụ: ~p(~"ababab"~)=~"3ab", ~p(~"aaaaaaaaaaaa"~)=~"6aa" hoặc "12a", ~p(~"abc"~)=~"1abc".

Với ~|s|~ là kích thước của xâu ~s~

Yêu cầu: Hãy chia xâu ~s~ thành các xâu con liên tiếp ~s_1,s_2,...,s_k~ và nén chúng sao cho tổng độ dài các xâu sau khi nén các xâu là bé nhất

Input

Dữ liệu vào từ file văn bản compstr.inp

Một dòng duy nhất chứa xâu kí tự ~s~ (~|s|\le 5000~). Dữ liệu đảm bảo xâu ~s~ chỉ gồm các chữ cái tiếng Anh in thường.

Output

Kết quả in ra file văn bản compstr.out

In ra một số nguyên duy nhất là tổng độ dài các xâu nén trong phương án tìm được.

Scoring

Sample Input 1

ababbbbaba

Sample Output 1

8

Sample Input 2

ttuxtuxtxtaba

Sample Output 2

12

Notes

Ở ví dụ thứ nhất, xâu ~s~ được chia thành ~3~ xâu con liên tiếp: "abab", "bb" và "baba"

• ~p~("abab") = "2ab"

• ~p~("bb") = "2b"

• ~p~("baba") = "2ba"

Tổng độ dài các xâu con sau khi nén bằng ~8~.