문자열 주기

문자열 S의 최소 주기를 구한다. 최소 주기 p란, 모든 i에 대해 S[i] = S[i mod p]가 성립하는 가장 작은 양의 정수이다. KMP failure function을 이용한다.

입력

첫째 줄에 문자열이 주어진다. (1 ≤ 길이 ≤ 1,000,000, 소문자 알파벳)

출력

문자열의 최소 주기를 출력한다.

예제 입력 1

abababab

예제 출력 1

2