该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

【问题描述】
其实在开考前半个小时题面并不是这样的。
由于明天要考试，同学们要把抽屉里的书都搬空，书很多而且办了走读不能回寝室的学长一眼就看到了回班撩他的学姐，于是就把学姐当学长用♂了：“帮我把这摞书搬走OvO”。
学姐筋疲力尽地抱着沉重的一摞书回到了机房，出于无聊她翻开了学长的字典。
学长的字典由一个字符串组成。对于两个字符串a和b，如果a既是b的前缀也是b的后缀，那么称a和b“相似”，空字符串和任何字符串相似。一个字符串可以通过编辑变换成一个比它短而且与它相似的字符串，付出的代价为这两个字符串的长度之差的平方。两个字符串通过编辑而变为同一个字符串所花费的最小代价被称为最短编辑距离。
给定学长的字典，现在学姐想知道这个字符串的每一对前缀的最短编辑距离中的最大值是多少。请你帮助劳累的紫萱学姐解决这个问题。
【输入】
一个字符串，仅包含小写英文字母。
【输出】
这个字符串每一对前缀中最长的最短编辑距离。
【输入输出样例1】
savemzx.in savemzx.out
abcab
23
【输入输出样例2】
savemzx.in savemzx.out
提供大样例 提供大样例
【数据范围】
最短编辑距离最长的一对前缀是abca和abcab，最短变换过程如下（箭头中的数字为过程的代价）
“abca”-9->“a”-1->（空字符串）
“abcab”-9->“ab”-4->“”
对于40%的数据，n≤500。
对于70%的数据，n≤5000。
对于100%的数据，n≤1000000，n为字符串长度。