A string is a finite sequence of lower-case (non-capital) letters of the English alphabet. Particularly, it may be an empty sequence, i.e. a sequence of $0$ letters. By $A = BC$ we denotes that $A$ is a string obtained by concatenation (joining by writing one immediately after another, i.e. without any space, etc.) of the strings $B$ and $C$ (in this order). A string $P$ is a prefix of the string $A$, if there is a string $B$, that $A = PB$. In other words, prefixes of $A$ are the initial fragments of $A$. In addition, if $P \ne A$ and $P$ is not an empty string, we say, that P is a proper prefix of $A$.

A string $Q$ is a period of $A$, If $Q$ is proper prefix of $A$ and $A$ is a prefix (not necessarily a proper one) of the string $QQ$. For example, the strings abab and ababab are both periods of the string abababa. The maximum period of a string $A$ is the longest of its periods or the empty string, If $A$ doesn't have any period. For example, the maximum period of ababab is abab. The maximum period of abc is the empty string.

Task

Write a programme that:

• reads from the standard input the string's length and the string itself,
• calculates the sum of lengths of maximum periods of all its prefixes,
• writes the result to the standard output.

Input

In the first line of the standard input there is one integer $k$ ($1 ≤ k ≤ 1\,000\,000$) - the length of the string. In the following line a sequence of exactly $k$ lower-case letters of the English alphabet is written - the string.

Output

In the first and only line of the standard output your programme should write an integer - the sum of lengths of maximum periods of all prefixes of the string given in the input.

Example

Input

8
babababa

Output

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$