题目描述

一个字符串是由小写英文字母组成的有限序列。特别地，它也可以是空序列（即长度为 $0$ 的序列）。

如果字符串 $A$ 是通过字符串 $B$ 和 $C$ 按顺序连接（中间没有任何间隔符号）得到的，我们表示为 $A=BC$ 。

如果存在一个字符串 $B$ 使得 $A=PB$ ，那么字符串 $P$ 是字符串 $A$ 的前缀。此外，如果 $P \neq A$ 且 $P$ 不是空字符串，我们称 $P$ 是 $A$ 的真前缀。

如果 $Q$ 是 $A$ 的真前缀，并且 $A$ 是字符串 $QQ$ 的前缀（不一定是真前缀），那么字符串 $Q$ 是 $A$ 的周期。例如，字符串 abab 和 ababab 都是 abababa 的周期。

字符串 $A$ 的最大周期是其最长的周期，如果 $A$ 没有周期，则为空字符串。例如，ababab 的最大周期是 abab；abc 的最大周期是空字符串。

编写一个程序，计算该字符串所有前缀的最大周期长度之和。

输入格式

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

接下来的一行包含一个由 $k$ 个小写英文字母组成的字符串。

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

8
babababa

对于所有数据， $1\le k\le10^6$ 。