← 返回题目列表

Codeforces · 1827/C

C. 回文分区

中文机器翻译题面 查看原题

子字符串是给定字符串中连续且非空的字母段,没有任何重新排序。

偶数回文是向后读与向前读相同且长度为偶数的字符串。例如,字符串“zz”、“abba”、“abccba”甚至是回文,但字符串“codeforces”、“reality”、“aba”、“c”则不是。

一个漂亮的字符串是一个偶回文,或者是一个可以分割成一些更小的偶回文的字符串。

给定一个字符串 $$$s$$$,由 $$$n$$$ 小写拉丁字母组成。计算 $$$s$$$ 的漂亮子串的数量。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 5\cdot 10^5$$$)。

每个测试用例的第二行包含一个字符串$$$s$$$。字符串 $$$s$$$ 仅由小写拉丁字母组成,长度为 $$$n$$$。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$5\cdot 10^5$$$。

输出

对于每个测试用例,打印漂亮子字符串的数量。

示例

输入 #1

6
6
abaaba
1
a
2
aa
6
abcdef
12
accabccbacca
6
abbaaa

输出 #1

3
0
1
0
14
6

注意

在第一个测试用例中,漂亮的子字符串是“abaaba”、“baab”、“aa”。

在最后一个测试用例中,漂亮的子字符串是“aa”(数了两次)、“abba”、“bb”、“bbaa”、“abbaaa”。