The Collean military communicates by encoding their messages through their Zagonetka machine. The codebreakers in The Alliance are trying desperately to crack the code and effectively end the war. The codebreakers managed to obtain an encoded message of length ~N~ consisting of lowercase English letters and they believe that it is the key to breaking the Collean's Zagonetka machine. They decide that a substring of the message is special if it is both a prefix and a suffix of the message. To assess the likelihood that the Zagonetka machine will generate a special message, the codebreakers want to count the number of occurrences of each special substring. Help the codebreakers count the total number of special substrings in the encoded message. Note that two equal substrings are both counted if they appear in different positions.

Constraints

Subtask 1 [20%]

~1 \le N \le 200~

Subtask 2 [80%]

~1 \le N \le 200\,000~

Input Specification

The first line contains one integer, ~N~, the length of the encoded message.
The second line contains the encoded message, ~S~.

Output Specification

The single line of output should contain one integer, the total number of occurrences of special substrings.

Sample Input

6
aabaaa

Sample Output

9

There are ~9~ special substrings: there are ~5~ a, ~3~ aa, and ~1~ aabaaa.