Let $s$ be a given string of up to $10^6$ digits. Find the maximal $k$ for which it is possible to partition $s$ into $k$ consecutive contiguous substrings, such that the $k$ parts form a palindrome. More precisely, we say that strings $s_0, s_1, \dots , s_{k-1}$ form a palindrome if $s_ i = s_{k-1-i}$ for all $0\leq i < k$.
In the first sample case, we can split the string 652526 into $4$ parts as 6|52|52|6, and these parts together form a palindrome. It turns out that it is impossible to split this input into more than $4$ parts while still making sure the parts form a palindrome.
A nonempty string of up to $10^6$ digits.
Print the maximal value of $k$ on a single line.
Sample Input 1 | Sample Output 1 |
---|---|
652526 |
4 |
Sample Input 2 | Sample Output 2 |
---|---|
12121131221 |
7 |
Sample Input 3 | Sample Output 3 |
---|---|
123456789 |
1 |
Sample Input 4 | Sample Output 4 |
---|---|
132594414896459441321 |
9 |