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.
Subtask 1 [20%]
~1 \le N \le 200~
Subtask 2 [80%]
~1 \le N \le 200\,000~
The first line contains one integer, ~N~, the length of the encoded message.
The second line contains the encoded message, ~S~.
The single line of output should contain one integer, the total number of occurrences of special substrings.
There are ~9~ special substrings: there are ~5~
aa, and ~1~