ЗИМ откри нов начин на компресија на текст кој содржи само мали латинични букви. Нека ја користиме буквата 'R' за да означиме "повтори го претходниот текст". Делот која треба да се повтори ќе биде делот од појавувањето на најблиската претходна 'M' (или од почеток на текстот – доколку нема ниту едно 'M' пред соодветното 'R').

На пример, "abcabcdabcabcdxyxyz" може да се компресира во "abcRdRMxyRz", "aaaaaaaa" во "aRRR" или "aaRR", итн. За да се декомпресира "abcRdRMxyRz", прво 'abc' се повторува за да стане 'abcabc', па се додава 'd', и потоа се тоа се повторува за да го добиеме текстот "abcabcdabcabcd". Ова е проследено со додавање на "xy", па негово повторување, и на крај додавање на 'z'.

Напишете програма која за даден некомпресиран текст ќе го открие и отпечати минималниот број на знаци со кои текстот може да се изрази во RM компресирана форма. Се разбира, треба да ги броите и знаците 'R' и 'M'.

Влез

Во првиот и единствен ред е запишан еден стринг (низа од знаци) S, која го означува некомпресираниот текст. Стрингот S ќе биде составен само од мали латинични букви ('a'-'z') и нема да содржи повеќе од 50 знаци.

Излез

Излезот се состои од бараниот минимален број на знаци.

Ограничувања

Временско ограничување: 1 second
Мемориско ограничување: 64 megabytes

Примери

влез
aaaaaaaa

излез
4

влез
xyz

излез
3

влез
bcdcdcdcdxcdcdcdcd

излез
12

Објаснување за првиот пример: aRRR или aaRR

Објаснување за вториот пример: xyz

Објаснување за третиот пример: Еден начин на компресија е - bMcdRRxMcdRR