F. Сжатие строки
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Иван хочет написать письмо своему другу. Письмо — строка s, состоящая из строчных латинских букв.

К сожалению, как только Иван начал писать письмо, он понял, что оно слишком длинное, и писать его целиком придётся очень долго. Поэтому он хочет написать сжатую версию строки s вместо самой строки.

Сжатая версия строки s — последовательность строк c1, s1, c2, s2, ..., ck, sk, где ci — десятичная запись числа ai (без лидирующих нулей), а si — некоторая строка из строчных латинских букв. Если Иван запишет строку s1 ровно a1 раз, потом s2 ровно a2 раз, и так далее, у него получится строка s.

Длина сжатой версии равна |c1| + |s1| + |c2| + |s2|... |ck| + |sk|. Среди всех сжатых версий Иван хочет выбрать такую, что её длина минимальна. Помогите Ивану определить минимально возможную длину.

Входные данные

В единственной строке входных данных записана строка s, состоящая из строчных латинских букв (1 ≤ |s| ≤ 8000).

Выходные данные

Выведите одно целое число — минимальную длину сжатой версии строки s.

Примеры
Входные данные
aaaaaaaaaa
Выходные данные
3
Входные данные
abcab
Выходные данные
6
Входные данные
cczabababab
Выходные данные
7
Примечание

В первом примере Иван выберет следующую версию: c110, s1a.

Во втором примере Иван выберет следующую версию: c11, s1abcab.

В третьем примере Иван выберет следующую версию: c12, s1c, c21, s2z, c34, s3ab.