A. Beautiful Substrings
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

A string $$$s$$$ is beautiful if it can be expressed in the form:

$$$$$$s=t+t'+t$$$$$$

where:

  • $$$+$$$ is defined as the concatenation of strings;
  • $$$t$$$ is a non-empty string;
  • $$$t'$$$ is the reverse of $$$t$$$.

You are given a string $$$s$$$. Find the number of beautiful substrings of $$$s$$$.

Input

Each test contains multiple test cases. The first line of each test contains an integer $$$t$$$ ($$$1 \le t \le 10^5 $$$) — the number of test cases.

The first line of each test case contains an integer $$$n$$$ ($$$1 \le n \le 5 \cdot 10^5$$$) — the length of $$$s$$$.

The second line contains the string $$$s$$$ ($$$|s|=n$$$). It is guaranteed that $$$s$$$ consists of only lowercase English characters.

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

Output

For each test case, output the number of beautiful substrings of $$$s$$$.

Example
Input
2
6
baabba
5
zzzzz
Output
1
3