题目描述

对于一个仅含小写字母的字符串 $a$，$p$ 为 $a$ 的前缀且 $p\ne a$，那么我们称 $p$ 为 $a$ 的 proper 前缀。

规定字符串 $Q$（可以是空串）表示 $a$ 的周期，当且仅当 $Q$ 是 $a$ 的 proper 前缀且 $a$ 是 $Q+Q$ 的前缀。

例如 ab 是 abab 的一个周期，因为 ab 是 abab 的 proper 前缀，且 abab 是 ab+ab 的前缀。

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

输入格式

第一行输入一个数 $k$，表示字符串 $a$ 的长度。 第二行输入字符串 $a$。

输出格式

一行一个整数，表示$a$所有前缀的最大周期长度之和。

8
babababa

24

数据范围

$1$ $\le$ $k$ $\le$ $10^6$