Sum of Maximum Period Lengths

You are given a string consisting of lower-case letters. A string is defined as a finite sequence of lower-case letters (possibly empty). For any string A, a string P is called a prefix of A if there exists a string B such that A = P ; B. Moreover, if P is non-empty and not equal to A, it is called a proper prefix.

A string Q is said to be a period of A if:

[ \text{(i)}; Q \text{ is a proper prefix of } A \quad \text{and} \quad \text{(ii)}; A \text{ is a prefix of } Q Q. ]

In other words, if |A| = m and |Q| = k with 1 \le k < m, then Q is a period of A if and only if

[ A[i] = Q[i \mod k] \quad \text{for all } 0 \le i < m, ]

which is equivalent to the condition that the suffix of A of length (m-k) matches the prefix of Q of length (m-k), i.e.,

[ A[k:m] = A[0:m-k]. ]

The maximum period of a string A is defined as the longest string Q satisfying the above conditions; if no such Q exists, the maximum period is the empty string. For example, the maximum period of "ababab" is "abab", and for "abc" it is the empty string.

Your task is to compute the sum of the lengths of the maximum periods of all prefixes of a given string. Note that all non-empty prefixes of the input string must be considered.

For instance, if the string is "ababab", its non-empty prefixes and the lengths of their maximum periods are:

• "a" (\rightarrow 0)
• "ab" (\rightarrow 0)
• "aba" (\rightarrow 2) (maximum period "ab")
• "abab" (\rightarrow 2) (maximum period "ab")
• "ababa"(\rightarrow 4) (maximum period "abab")
• "ababab"(\rightarrow 4) (maximum period "abab")

Thus, the sum is (0 + 0 + 2 + 2 + 4 + 4 = 12).

inputFormat

The input consists of two lines. The first line contains an integer (n) representing the length of the string. The second line contains the string itself, which is composed of lower-case letters.

outputFormat

Output a single integer representing the sum of the lengths of the maximum periods of all non-empty prefixes of the given string.

sample

3
abc

0