Isomorphic Inversion

Time limit1sMemory limit512 MB

Summary

Split a digit string into the largest number of contiguous pieces whose sequence of pieces reads the same forward and backward.

Level: Hard8 of 10
Topics: Greedy, String matching, Two pointers, Hash map
Solved: No attempts yet

Problem

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, \ldots, s_{k-1}$ form a palindrome if $s_i = s_{k-1-i}$ for all $0 \le 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.

Input

A nonempty string of up to $10^6$ digits.

Output

Print the maximal value of $k$ on a single line.

Examples4

Example 1
Input
```
652526
```
Expected output
```
4
```
Example 2
Input
```
12121131221
```
Expected output
```
7
```
Example 3
Input
```
123456789
```
Expected output
```
1
```
Example 4
Input
```
132594414896459441321
```
Expected output
```
9
```