Palindrome Degree

길이가 n인 문자열 s가 그 자체로 팰린드롬이고, 길이가 인 접두사와 접미사가 (k - 1)-팰린드롬이면 s를 k-팰린드롬이라고 한다. 정의에 따라 모든 문자열은 빈 문자열까지 포함하여 0-팰린드롬이다.

문자열 s가 k-팰린드롬이 되게 하는 최대 수 k를 s의 팰린드롬 차수라고 하자. 예를 들어, "abaaba"의 차수는 3이다.

문자열 하나가 주어진다. 모든 접두사의 팰린드롬 차수의 합을 구해야 한다.

입력 데이터의 첫 번째 줄에는 라틴 문자와 숫자로 구성된 비어 있지 않은 문자열이 주어진다. 문자열의 길이는 5·106을 초과하지 않는다. 문자열은 대소문자를 구분한다.

문자열의 모든 접두사의 팰린드롬 차수의 합인 유일한 수를 출력한다.