팰린팰린드롬

왼쪽에서 오른쪽으로 읽은 결과와 오른쪽에서 왼쪽으로 읽은 결과가 동일한 문자열을 팰린드롬이라고 한다. 예를 들어, ABBA는 팰린드롬이고, PICKLE은 팰린드롬이 아니다.

민기는 어느 날 "꼬들꼬들한 꼬들꼬들"이라는 문자열을 봤는데, 공백을 제거하고 "꼬들"을 묶어서 하나로 생각하면 팰린드롬이 된다는 생각을 했다. 이것이 너무 감명 깊었던 민기는 이러한 분할을 팰린팰린분할이라고 정의하기로 결심했다. 구체적인 정의는 다음과 같다:

문자열 $S$가 있을 때, $S$를 비어 있지 않은 연속한 부분문자열 $K$개로 분할할 수 있다. 이때, 만약 $1\leq i \leq K $인 모든 $i$에 대해 $i$번째 부분문자열과 $K - i + 1$번째 부분문자열이 같다면, 그 분할 방법을 팰린팰린분할이라고 하자. 그리고, 분할된 $K$개의 부분문자열들의 길이의 최댓값을 팰린팰린분할의 크기라고 정의하자. 문자열 $S$의 모든 팰린팰린분할에 대하여, 팰린팰린분할의 크기의 최솟값이 $n$일 때, $S$를 $n$-팰린팰린드롬이라고 정의한다.

예를 들어, ABCDABC는 (ABC)(D)(ABC)와 같이 분할할 수 있고, 이때 부분문자열의 길이의 최댓값은 $3$이며, 크기가 $2$ 이하인 팰린팰린분할은 존재하지 않는다. 따라서 ABCDABC는 $3$-팰린팰린드롬이다.

민기의 정의를 토대로, 주어진 문자열이 $n$-팰린팰린드롬일 때, $n$의 값을 구해보자.

문자열 $S$가 주어진다. 이 문자열은 알파벳 대문자로만 이루어져 있다. ($1 \leq |S| \leq 500\,000$)

문자열 $S$가 $n$-팰린팰린드롬일 때, $n$의 값을 출력하라.

$|S|$는 문자열 $S$의 길이를 의미한다.