题目描述

如果一个字符串正着读和倒着读是一样的，则称它是回文的。

给定一个长度为 $N$ 的字符串 $S$，求它的最长回文子串的长度是多少。

输入格式

输入将包含最多 $30$ 个测试用例，每个测试用例占一行，以最多 $1000000$ 个小写字符的形式给出。

输入以一个以字符串 END 开头的行表示输入终止。

输出格式

对于输入中的每个测试用例，输出测试用例编号和最大回文子串的长度（参考样例格式）。

每个输出占一行。

样例

输入样例：

abcbabcbabcba
abacacbaaaab
END

输出样例：

Case 1: 13
Case 2: 6

样例解释

• 第一行字符串 abcbabcbabcba，整个字符串就是回文的，长度为 13。
• 第二行字符串 abacacbaaaab，最长回文子串为 baaaab，长度为 6。

数据范围

• 最多 30 个测试用例
• 每个字符串长度不超过 $10^6$

时空限制

• 时间限制：1 秒
• 空间限制：64 MB