A15904 | 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$ .

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$ .

For each test case print the number of beautiful substrings.