题目描述

字符串是由有限个小写英文字母组成的序列，空字符串也视为字符串。

如果存在字符串 $B$，使得 $A=PB$，那么字符串 $P$ 是字符串 $A$ 的前缀。如果 $P\ne A$ 且 $P$ 不是空字符串，那么 $P$ 是 $A$ 的真前缀。

如果字符串 $Q$ 是 $A$ 的真前缀，并且 $A$ 是 $QQ$ 的前缀，那么称 $Q$ 是 $A$ 的周期。字符串 $A$ 的最大周期是它最长的周期；如果 $A$ 没有周期，则最大周期为空字符串。

例如，abab 和 ababab 都是 abababa 的周期，其中最大周期是 ababab；字符串 abc 的最大周期为空字符串。

给定一个字符串，求它的所有前缀的最大周期长度之和。

输入格式

第一行包含一个整数 $k$，表示字符串的长度。

第二行包含一个长度为 $k$、仅由小写英文字母组成的字符串。

输出格式

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

样例

8
babababa

24

数据范围与提示

• $1 < k < 10^6$

来源

一本通 2.2 练习 2，POI 2006