Description

A string that reads the same forward and backward is called a palindrome. For example, acbca is a palindrome, while abc is not: the forward order is abc, and the reverse is cba, which are not the same.

Given a string $S$ of length $n$, find the longest double palindromic substring $T$ of $S$, that is, $T$ can be divided into two parts $X, Y$ (with $|X|, |Y| \ge 1$) and both $X$ and $Y$ are palindromes.

Input Format

One line containing a string $S$ consisting of lowercase English letters.

Output Format

One line with a single integer, the length of the longest double palindromic substring.

baacaabbacabb

12

Hint

Sample Explanation

Starting from the second character, the string aacaabbacabb can be split into two parts aacaa and bbacabb, and both are palindromes.

Constraints

For $100\%$ of the testdata, $2 \le |S| \le 10^5$.

2018.12.10, 2018.12.15: Thanks to @Ycrpro for providing two hack testdata sets.

Translated by ChatGPT 5