Một xâu được gọi là đối xứng, nếu nó đọc ngược cũng giống như đọc xuôi. Ví dụ các xâu ~"z", "aa", "abba", "madam"~ là đối xứng và các xâu ~"ab", "abc", "abab"~ là không đối xứng.

Một xâu được gọi là đối xứng đôi, nếu nó được tạo thành bằng cách ghép hai xâu đối xứng có độ dài bằng nhau. Ví dụ các xâu ~"ab", "aabb", "aaaa"~ là đối xứng đôi và các xâu ~"aaa", "abba"~ và ~"aaaabb"~ là không đối xứng đôi.

Cho trước một xâu ~s~, bạn hãy viết một chương trình đếm xem có bao nhiêu xâu con của ~s~ là đối xứng đôi. Nói cách khác, có bao nhiêu cặp ~(l, r)~ sao cho xâu con ~s_l s_{l+1} \dots s_r~ là đối xứng đôi.

Ví dụ, xâu ~s = "abacac"~ có ~6~ xâu con đối xứng đôi là: ~"ab", "ba", "ac", "ca", "ac", "abacac"~.

Input

• Dòng đầu tiên chứa số nguyên dương ~n~ (~1 \le n \le 5 \times 10^5~) là độ dài xâu ~s~.
• Dòng thứ hai chứa xâu ~s~ bao gồm các chữ cái tiếng Anh viết thường.

Output

• Một số nguyên là số xâu con đối xứng đôi của xâu ~s~.

Sample Input 1

6
abacac

Sample Output 1

6

Sample Input 2

1
e

Sample Output 2

0

Sample Input 3

5
aaaaa

Sample Output 3

6

Subtasks