Задана строка s, состоящая из n строчных латинских букв. Вам необходимо набрать эту строку на вашей клавиатуре.
Изначально у вас есть пустая строка. Пока вы не набрали необходимую строку, вы можете применять следующую операцию:
- дописать символ в конец строки.
Кроме того, не более одного раза вы можете применить дополнительную операцию: cкопировать строку и приписать её к самой себе.
Например, если вы хотите набрать строку abcabca, вы можете набрать её за 7 операций, если будете выписывать символы один за другим. Или вы можете набрать её за 5 операций, если вы сначала наберёте строку abc, затем скопируете её и допишете последний символ.
Если вам нужно набрать строку aaaaaaaaa, наилучший вариант — набрать 4 символа первой операцией, потом скопировать и приписать строку, и затем дописать последний символ.
Выведите минимальное количество операций, которое необходимо, чтобы набрать заданную строку.
Выходные данные
Выведите единственное целое число — минимальное количество ходов, которое необходимо, чтобы набрать заданную строку.
Примечание
Первый тест описан в условии задачи.
Во втором тесте вы можете только выписывать символы один за другим.