C. Quasi-Palindrome
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Ana, affectionately called Anita, loves palindromes, but unfortunately she is constantly sad because palindromes are rare and she has little to no opportunity to exercise her passion. For example, Mexico, where Ana lives, is known for having no city whose name is a palindrome.

Instead of looking for another hobby, Ana is considering slightly extending her passion to include quasi-palindromes. A word is a quasi-palindrome if there are at most two positions that differ between the word and its reverse.

For example, the word $$$anita$$$ is a quasi-palindrome because $$$anita$$$ differs from $$$atina$$$ in only two positions. However, $$$mexico$$$ is not a quasi-palindrome, as it differs from $$$ocixem$$$ in 6 positions. Note that every palindrome is also a quasi-palindrome.

Ana realized that her life could greatly improve if she makes this decision. She has plans to move to Zapopan near Guadalajara and won't be bothered when her friends call her Anita.

Before making this decision, she needs to be sure that she won't regret it and wants to understand more about the properties of quasi-palindromes. For this, she wants you to write a program that, given a word, calculates how many substrings of that word are quasi-palindromes.

Input

An integer $$$n$$$ ($$$1 \leq n \leq 10^5$$$), the size of the word $$$s$$$. A word $$$s, |s| = n$$$, composed only of lowercase letters ([a-z]).

Output

A number, the number of substrings of $$$s$$$ that are quasi-palindromes.

Examples
Input
5
anita
Output
13
Input
6
mexico
Output
15
Input
7
abacaba
Output
22
Note

In the first test case, out of all 15 substrings of $$$anita$$$, only $$$anit$$$ and $$$nita$$$ are not quasi-palindromes because they differ by 4 positions from their reverses.

In the second case, all and only the substrings of size 3 or less are quasi-palindromes, totaling 15 quasi-palindrome substrings.