This is the hard version of this problem. The only difference between the easy and hard versions is what you are asked to find.

Yuki is a literary scholar!

She defines a string consisting only of lowercase letters as lovely if and only if:

• The number of characters that appear an odd number of times in the string is even.
• The number of characters that appear a positive even number of times in the string is odd.

For example, $\texttt{lovely}$ and $\texttt{milmon}$ are lovely, while $\texttt{dxqwq}$ and $\texttt{cocoly}$ are not lovely.

Now, Yuki has a string $s$ of length $n$ consisting only of lowercase letters. You need to help her find the number of pairs $(l, r)$ such that:

• $1 \le l \le r \le n$.
• The substring $s_l\dots s_r$ is lovely.

Input

This problem contains multiple test cases.

The first line contains a positive integer $t\ (1 \le t \le 10^5)$, representing the number of test cases.

For each test case:

• The first line contains a positive integer $n\ (1 \le n \le 5\cdot10^5)$.
• The second line contains a string $s$ of length $n$.

It is guaranteed that the string $s$ contains only lowercase letters, and the sum of $n$ over all test cases does not exceed $5 \cdot 10^5$.

Output

For each test case, output a single line containing an integer representing the number of pairs $(l, r)$ that satisfy the conditions.

Examples

Input 1

8
5
hello
6
lovely
6
milmon
5
dxqwq
6
cocoly
6
qingyu
9
coffeezzz
6
byebye

Output 1

3
1
2
1
1
0
10
4

Note

For the first test case:

• In $\texttt{ll}$, the number of characters appearing an odd number of times is $0$, and the number of characters appearing a positive even number of times is $1$. Thus, $\texttt{ll}$ is lovely, and $(3, 4)$ is a valid pair.
• In $\texttt{hell}$, the number of characters appearing an odd number of times is $2$, and the number of characters appearing a positive even number of times is $1$. Thus, $\texttt{hell}$ is lovely, and $(1, 4)$ is a valid pair.
• In $\texttt{ello}$, the number of characters appearing an odd number of times is $2$, and the number of characters appearing a positive even number of times is $1$. Thus, $\texttt{ello}$ is lovely, and $(2, 5)$ is a valid pair.
• It can be proven that no other pairs satisfy the conditions, so the answer is $3$.

For the second test case:

• In $\texttt{lovely}$, the number of characters appearing an odd number of times is $2$, and the number of characters appearing a positive even number of times is $4$. Thus, $\texttt{lovely}$ is lovely, and $(1, 6)$ is a valid pair.
• It can be proven that no other pairs satisfy the conditions, so the answer is $1$.