Cave Paintings

Doctor Braveston and his group found an ancient cave in Jumanji. A string $s$ of lowercase Latin letters was written on its wall. To continue, the explorers must find the length of the longest palindrome that is a substring of some cyclic shift of $s$.

A palindrome is a string that reads the same forward and backward. For example, abacaba, abba, and q are palindromes. A substring is a contiguous run of characters from a string. A cyclic shift is formed by cutting a prefix from the string and appending it to the end. For example, bacabaa, cabaaba, and abacaba are cyclic shifts of abacaba.

The input is a single non-empty line containing the string $s$. The string consists of lowercase Latin letters only, and its length does not exceed $10^6$.

Print one integer, the maximum length of a palindrome that is a substring of some cyclic shift of $s$.