对于一个仅含小写字母的字符串a，p为 a的前缀且p=a，那么我们称 p为 a 的 proper前缀。
规定字符串 Q表示a的周期，当且仅当 Q 是 a的proper前缀且 a 是 Q+Q 的前缀。若这样的字符串不存在，则 a 的周期为空串。
例如 Q:ab 是 a:abab 的一个周期，因为 Q 是 a的 proper 前缀，且Q+Q:abab是a的前缀。
求给定字符串所有前缀的最大周期长度之和。

的第一行中有一个整数k（1≤k≤1000 000）表示字符串的长度。
下面的一行中，输入这个序列（英语字母表中的k个小写字母）。

输出一行一个整数，表示给定字符串的所有前缀的最大周期长度的总和。

样例解释：
b 0
ba 0
bab 2（Q：ba，a：bab，Q+Q：baba；Q是a的前缀，a是Q+Q的前缀，故最大周期长度为2）
baba 2
babab 4
bababa 4
bababab 6
babababa 6