You are given a string $S$ of length $N$. A string is called twin if the characters of the string can be split into two groups such that the occurrence of each character is equal in both groups.

Find the number of twin substrings of $S$.

Input Format:

• The first line contains an integer $T$, denoting the number of test cases.
• The first line of each test case contains an integer $N$, denoting the length of the string $S$.
• The second line of each test case contains the string $S$.

Output Format:

For each test case, print the number of twin substrings of $S$.

Constraints:

$1 <= T <= 10$

$1 <= N <= 10^5$

$S$ contains lower-case English letters