시간 제한메모리 제한제출정답맞힌 사람정답 비율
6 초 1024 MB0000.000%

문제

Для передачи сообщений отряд Китнисс использует свою уникальную шифровку. Шифровка представляет собой повторение сообщения некоторое ненулевое число раз и дописывание префикса (возможно, пустого) исходного сообщения в конец шифровки. Например, сообщение <<hello>> можно закодировать как <<hellohellohell>>, как <<hellohellohe>>, а также например как <<hellohellohello>>.

Недавно Китнисс получила зашифрованное сообщение и сразу поняла, что с ним что-то не так. Видимо, при передаче возникла какая-то ошибка и в где-то добавился лишний символ. Теперь Китнисс хочет понять, каким же все-таки было исходное сообщение, но так как точно сейчас сказать это невозможно, она хочет узнать минимальную длину сообщения, которое могло быть закодировано. Например, если Китнисс получила зашифрованное сообщение <<abadbab>>, она может понять, что в середине сообщения есть лишний символ <<d>> и минимальная длина закодированного сообщения равна 2.

입력

В единственной строке находится непустая строка из строчных латинских букв, длина которой хотя бы 2 и не превосходит $10^6$.

출력

В единственной строке выведите минимальную длину сообщения.

예제 입력 1

abba

예제 출력 1

2

예제 입력 2

abadbab

예제 출력 2

2

예제 입력 3

daaa

예제 출력 3

1