题目描述

给定一个长度为 $N$ 的字符串 $S$，请你计算 $S$ 中有多少个连续子串是回文串。

输入格式

第一行：一个正整数 $N$，表示字符串的长度。
第二行：一个长度为 $N$ 的字符串 $S$。

输出格式

输出一个整数，表示回文子串的个数。

样例

3
aba

4

2
aa

3

样例解释

• 样例1：字符串 "aba" 的回文子串有 "a", "b", "a", "aba"，共4个。
• 样例2：字符串 "aa" 的回文子串有 "a", "a", "aa"，共3个。

数据范围

• 对于 60% 的数据：$1 \le N \le 100$。
• 对于 100% 的数据：$1 \le N \le 2000$。