C. Palindrome Partition
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

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

Input

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

Output

For each test case print the number of beautiful substrings.

Example
Input
6
6
abaaba
1
a
2
aa
6
abcdef
12
accabccbacca
6
abbaaa
Output
3
0
1
0
14
6
Note

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