子字符串是给定字符串中连续且非空的字母段,没有任何重新排序。
偶数回文是向后读与向前读相同且长度为偶数的字符串。例如,字符串“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”。