字符串是由有限个小写英文字母组成的序列。特别地，它可以是一个空序列，即包含 $0$ 个字母的序列。记 $A = BC$ 表示字符串 $A$ 是通过将字符串 $B$ 和 $C$ 连接（即按顺序首尾相接，中间不加任何空格等）得到的。如果存在字符串 $B$ 使得 $A = PB$，则称字符串 $P$ 是字符串 $A$ 的前缀。换句话说，$A$ 的前缀是 $A$ 的初始片段。此外，如果 $P \ne A$ 且 $P$ 不是空字符串，则称 $P$ 是 $A$ 的真前缀。

如果 $Q$ 是 $A$ 的真前缀，且 $A$ 是字符串 $QQ$ 的前缀（不一定是真前缀），则称字符串 $Q$ 是 $A$ 的周期。例如，字符串 abab 和 ababab 都是字符串 abababa 的周期。字符串 $A$ 的最大周期是其所有周期中最长的一个；如果 $A$ 没有周期，则最大周期为空字符串。例如，ababab 的最大周期是 abab，而 abc 的最大周期是空字符串。

任务

编写一个程序：

• 从标准输入读取字符串的长度及字符串本身，
• 计算该字符串所有前缀的最大周期长度之和，
• 将结果写入标准输出。

输入格式

标准输入的第一行包含一个整数 $k$ ($1 \le k \le 1\,000\,000$)，表示字符串的长度。下一行包含一个由 $k$ 个小写英文字母组成的序列，即该字符串。

输出格式

在标准输出的第一行（也是唯一一行）中，输出一个整数，表示输入字符串的所有前缀的最大周期长度之和。

样例

输入 1

8
babababa

输出 1

24

说明

$P_8 = 6$, $P_7 = 6$, $P_6 = 4$, $P_5 = 4$, $P_4 = 2$, $P_3 = 2$, $P_2 = 0$, $P_1 = 0$