Description

Original source: POI 2006

A string is a finite sequence of lowercase letters. Specifically, an empty sequence can also be considered a string. A string $P$ is a prefix of string $A$ if and only if there exists a string $B$ such that $A = PB$. If $P \not = A$ and $P$ is not an empty string, then we say $P$ is a proper prefix of $A$.

We define $Q$ as a period of $A$ if and only if $Q$ is a proper prefix of $A$ and $A$ is a prefix of $QQ$ (not necessarily a proper prefix). For example, the strings abab and ababab are both periods of the string abababa. The maximum period of string $A$ is its longest period or an empty string (when $A$ has no periods). For instance, the maximum period of ababab is abab, and the maximum period of abc is an empty string.

Given a string, calculate the sum of the lengths of the maximum periods for all its prefixes.

Input Format

The first line contains an integer $k$, the length of the string.

The next line contains the given string.

Output Format

Output an integer representing the sum of the lengths of the maximum periods for all prefixes of the string.

Sample 1

8
babababa

24

Data Range and Hint

For all data, $1 < k < 10^6$.