Хлоя хочет написать письмо своей подруге. Письмо - строка s, состоящая из строчных латинских букв.
К сожалению, как только Хлоя начала писать письмо, она поняла, что оно слишком длинное, и писать его целиком придётся очень долго. Поэтому она хочет написать сжатую версию строки s вместо самой строки.
Сжатая версия строки s — последовательность строк c
1, s
1, c
2, s
2, ..., c
k, s
k, где c
i — десятичная запись числа a
i (без лидирующих нулей), а s
i — некоторая строка из строчных латинских букв. Если Хлоя запишет строку s
1 ровно a
1 раз, потом s
2 ровно a
2 раз, и так далее, у нее получится строка s.
Длина сжатой версии равна |c
1| + |s
1| + |c
2| + |s
2|... |c
k| + |s
k|. Среди всех сжатых версий Хлоя хочет выбрать такую, что её длина минимальна. Помогите Хлое определить минимально возможную длину.
Входные данные:
В единственной строке входных данных записана строка s, состоящая из строчных латинских букв (1 ≤ |s| ≤ 5000).
Выходные данные:
Выведите одно целое число — минимальную длину сжатой версии строки s.
Примеры:
| Входные данные |
Выходные данные |
| aaaaaaaaaa |
3 |
| abcab |
6 |
| cczabababab |
7 |
Пояснения:
В первом примере Хлоя выберет следующую версию: c
1 — 10, s
1 — a.
Во втором примере Хлоя выберет следующую версию: c
1 — 1, s
1 — abcab.
В третьем примере Хлоя выберет следующую версию: c
1 — 2, s
1 — c, c
2 — 1, s
2 — z, c
3 — 4, s
3 — ab.