CF1827C.Palindrome Partition

A substring is a continuous and non-empty segment of letters from a given string, without any reorders.

An even palindrome is a string that reads the same backward as forward and has an even length. For example, strings "zz", "abba", "abccba" are even palindromes, but strings "codeforces", "reality", "aba", "c" are not.

A beautiful string is an even palindrome or a string that can be partitioned into some smaller even palindromes.

You are given a string $s$, consisting of $n$ lowercase Latin letters. Count the number of beautiful substrings of $s$.

子串是从给定字符串中取出的一个连续且非空的字母段，不进行任何重排。

偶回文串是指正读与反读都相同、且长度为偶数的字符串。例如，字符串 "zz"、"abba"、"abccba" 是偶回文串，但字符串 "codeforces"、"reality"、"aba"、"c" 不是。

优美字符串是指：它本身是一个偶回文串，或者它可以被划分为若干个更小的偶回文串。

给你一个由 $n$ 个小写拉丁字母组成的字符串 $s$。请统计 $s$ 中优美子串的个数。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($1 \le n \le 5\cdot 10^5$).

The second line of each test case contains a string $s$. String $s$ consists of only lowercase Latin letters and has a length of $n$.

It is guaranteed that the sum of $n$ over all test cases does not exceed $5\cdot 10^5$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^4$）。随后是各测试用例的描述。

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

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

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

For each test case print the number of beautiful substrings.

对于每个测试用例，输出优美子串的数量。

In the first test case, the beautiful substrings are "abaaba", "baab", "aa".

In the last test case, the beautiful substrings are "aa" (counted twice), "abba", "bb", "bbaa", "abbaaa".

在第一个测试用例中，优美的子字符串有 "abaaba"、"baab" 和 "aa"。

在最后一个测试用例中，优美的子字符串有 "aa"（计算两次）、"abba"、"bb"、"bbaa" 和 "abbaaa"。