Periods of Words

A string (P) is considered a prefix of a string (A) if (A = PB), where either (P) or (B) can be empty. A string (P) is a non-trivial prefix of (A) if (A = PB), and neither (P) nor (B) are empty. A string (Q) is termed a period of the string (A) if (Q) is a non-trivial prefix of (A) and (A) is a prefix (though not necessarily a non-trivial one) of the string (QQ). For instance, the strings (abab) and (ababab) are periods of the string (abababa).

The maximum period of a string (A) is the longest among its periods, or an empty string if (A) has no periods. For example, the maximum period of the string (ababab) is (abab), and the maximum period of the string (abc) is an empty string.

Write a program that calculates the sum of the lengths of the maximum periods for all prefixes of the given string (A).

Input

The first line of the input contains a single integer (k) ((1 $\le$ k $\le$ 1000000)) – the length of the string (A). The second line contains a sequence of (k) lowercase letters from the English alphabet – the string (A).

Output

Output a single integer on one line – the sum of the lengths of the maximum periods of each prefix of the string (A).

Examples