Description

一个字符串是由小写英文字母组成的有限序列。特别地，它也可以是空序列（即长度为 $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 的最大周期是空字符串。

任务：

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

Input Format

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

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

Output Format

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

8
babababa

24

Hint

（由 Gemini 2.5 Flash 翻译，人工审核）

数据范围

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