Một xâu được gọi là xâu đối xứng (xâu palindrome) nếu xâu đó không thay đổi khi viết theo chiều xuôi (từ trái sang phải) hay chiều ngược (từ phải sang trái). Trong tất cả các xâu đối xứng, một xâu sẽ được gọi là siêu đối xứng nếu các kí tự của chúng ở vị trí chẵn bằng nhau.

Yêu cầu: từ xâu ~s~ cho trước, hãy đếm số lượng xâu con liên tiếp là xâu siêu đối xứng.

Input

• Dòng đầu tiên gồm số nguyên ~n~ ~(1 \le n \le 2 \cdot 10^5)~ - độ dài của xâu ~s~.

• Dòng thứ hai gồm xâu ~s~ có độ dài ~n~, các kí tự trong xâu ~s~ là các kí tự tiếng Anh in thường.

Output

• In ra số lượng xâu con liên tiếp siêu đối xứng của xâu ~s~.

Scoring

• ~30\%~ số test thoả mãn ~n \le 500~.

• ~30\%~ số test khác thoả mãn ~n \le 5000~.

• ~40\%~ số test còn lại không có ràng buộc gì thêm.

Sample Input 1

5
abcba

Sample Output 1

7

Notes

Trong test ví dụ trên, các xâu con liên tiếp siêu đối xứng là ~[1, 1], [2, 2], [3, 3], [4, 4], [5, 5], [2, 4], [1, 5]~.