CF1827C Palindrome Partition

子串是指给定字符串中连续且非空的一段字母，且不改变原有顺序。 偶数回文串是指长度为偶数且正着读和反着读都相同的字符串。例如，字符串 "zz"、"abba"、"abccba" 是偶数回文串，但字符串 "codeforces"、"reality"、"aba"、"c" 不是。 美丽串是指偶数回文串，或者可以分割成若干个更小的偶数回文串的字符串。 给定一个由 $n$ 个小写拉丁字母组成的字符串 $s$，请你计算 $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$。

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

在第一个测试用例中，美丽子串为 "abaaba"、"baab"、"aa"。 在最后一个测试用例中，美丽子串为 "aa"（出现两次）、"abba"、"bb"、"bbaa"、"abbaaa"。 由 ChatGPT 4.1 翻译