题目描述

虾仁学习了很多字符串算法，比如马拉车、Z函数、字符串哈希、KMP、字典树、AC自动机、后缀自动机，那么接下来这个AK自动机你会吗？

给定一个字符串 $S$ ，请找出 $S$ 的一个前缀和后缀（前后缀长度必须相等，可以为空），使得它们拼接后是一个回文串$^\dagger$，请输出拼成的回文串最长长度。

$^\dagger$ 正着读和反着读一样的字符串。

输入格式

第一行一个字符串的 $S\ \left(1 \le |S| \le 3.1 \times 10^6\right)$，只包含小写字母。

输出格式

输出一个整数表示答案。

样例输入

abacba

样例输出

4

样例解释

选择前后缀长度为 $2$，选择前缀：$\text{ab}$，后缀：$\text{ba}$，它们可以拼成：$\text{abba}$ 是回文，并且长度为 $4$，可以证明这是最长的回文串。