Problem B
Casting Spells
Casting spells is the least understood technique of dealing with real life. Actually, people find it quite hard to distinguish between real spells like “abrahellehhelleh” (used in the battles and taught at the mage universities) and screams like “rachelhellabracadabra” (used by uneducated witches for shouting at cats). Finally, the research conducted at the Unheard University showed how one can measure the power of a word (be it a real spell or a scream). It appeared that it is connected with the mages’ ability to pronounce words backwards. (Actually, some singers were burned at the stake for exactly the same ability, as it was perceived as demonic possession.) Namely, the power of a word is the length of the maximum subword of the form $ww^ Rww^ R$ (where $w$ is an arbitrary sequence of characters and $w^ R$ is $w$ written backwards). If no such subword exists, then the power of the word is $0$. For example, the power of abrahellehhelleh is $12$ as it contains hellehhelleh and the power of rachelhellabracadabra is $0$. Note that the power of a word is always a multiple of $4$.
Input
The input is a single line containing a word of length $3 \cdot 10^5$, consisting of (large or small) letters of the English alphabet.
Output
You should output one integer $k$, the power of the word.
| Sample Input 1 | Sample Output 1 |
|---|---|
abrahellehhelleh |
12 |
| Sample Input 2 | Sample Output 2 |
|---|---|
rachelhellabracadabra |
0 |