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 of length 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”.
The first line contains a single integer , the number of test cases.
Each test case starts with an integer , the length of the given string. The next line contains the string .
Sum of over all test cases is no greater than .
For each test case print a single integer, which is the number of number of good substrings in .
5 3 AAA 1 P 2 PQ 2 PP 4 XOOY
2 0 0 1 1