回文划分

• 时间限制：1 秒
• 内存限制：256 MiB

题目描述

子串是一个字符串中连续且非空的一段字符。

长度为偶数的回文串称为偶回文串。例如，zz、abba 和 abccba 是偶回文串，而 codeforces、reality、aba 和 c 不是。

若一个字符串本身是偶回文串，或能被划分成若干个偶回文串，则称它为美丽串。

给定一个仅由小写拉丁字母组成的字符串 $s$，请计算 $s$ 的美丽子串数量。

输入格式

第一行一个整数 $t$，表示测试用例数量。

每个测试用例的第一行一个整数 $n$，表示字符串长度；第二行一个长度为 $n$ 的字符串 $s$。

输出格式

对每个测试用例输出一行一个整数，表示美丽子串数量。

样例输入 1

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

样例输出 1

3
0
1
0
14
6

数据范围

$1\le t\le10^4$，$1\le n\le5\cdot10^5$，所有测试用例的 $n$ 之和不超过 $5\cdot10^5$。