K. Two-Tone Palindromes
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a string $$$s$$$ consisting of lowercase English letters.

A string $$$p$$$ is a palindrome if $$$p_i = p_{|p|-i+1}$$$ for every $$$i$$$ ($$$1 \le i \le |p|$$$). A string is two-tone if it contains at most $$$2$$$ distinct characters.

Count the substrings of $$$s$$$ that are both palindromes and two-tone. Two substrings are considered different if their left endpoints or right endpoints differ.

Input

Each test file 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 10^6$$$), the length of the string.

The second line contains a string $$$s$$$ of length $$$n$$$ consisting of lowercase English letters.

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

Output

For each test case, print a single integer — the number of substrings that are both palindromes and two-tone.

Example
Input
2
5
ababa
6
abccba
Output
9
8
Note

In the first test case, every palindromic substring contains only the characters a and b. Therefore, the answer equals the total number of palindromic substrings, which is $$$9$$$.

In the second test case, the entire string abccba is a palindrome, but it contains $$$3$$$ distinct characters, so it is not counted.