최소 주기

캣니스의 분대는 고유한 암호문을 사용해 메시지를 전달한다. 암호문은 원래 메시지를 0이 아닌 몇 번 반복한 뒤, 원래 메시지의 접두사(비어 있을 수도 있음)를 끝에 덧붙인 것이다. 예를 들어 hello 메시지는 hellohellohell, hellohellohe, hellohellohello로 암호화할 수 있다.

캣니스는 최근 암호화된 메시지를 받았고, 무언가 잘못되었음을 바로 알아챘다. 전송 중 오류가 생겨 어딘가에 문자가 하나 더 들어간 것으로 보인다. 캣니스는 원래 메시지가 무엇이었는지 알고 싶지만 지금은 확실히 말할 수 없으므로, 암호화되었을 수 있는 메시지의 최소 길이를 구하려고 한다. 예를 들어 abadbab를 받았다면 가운데에 불필요한 문자 d가 있다는 것을 알 수 있고, 암호화된 메시지의 최소 길이는 2이다.

한 줄에 공백이 없는 비어 있지 않은 소문자 라틴 문자열이 주어진다. 문자열의 길이는 2 이상 $10^6$ 이하이다.

암호화되었을 수 있는 메시지의 최소 길이를 한 줄에 출력한다.