Just Another String Problem

A string is called good if the number of occurrence of every character in it is even. For example, “BB”, “XYXY” and “PRTRPT” are good strings. But “A”, “ABC” and “PRPQ” are not good strings.

Given a string $S$ of length $N$ consisting of only upper-case English letters, you need to count how many good substrings there are.

A substring is a contiguous sequence of characters within a string. Like “ABC”, “BC” and “B” are substrings of “ABC”. But ”AC” is not a substring of “ABC”.

Input

The first line contains a single integer $T$ $(1\leq T \leq100)$, the number of test cases.

Each test case starts with an integer $N$ $(1\leq N \leq10^5)$, the length of the given string. The next line contains the string $S$.

Sum of $N$ over all test cases is no greater than $3 \cdot 10^5$.

Output

For each test case print a single integer, which is the number of number of good substrings in $S$.

Sample

Input	Output
5 3 AAA 1 P 2 PQ 2 PP 4 XOOY	2 0 0 1 1