You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
A non-empty digit string is diverse if the number of occurrences of each character in it doesn't exceed the number of distinct characters in it.

For example:

- string "7" is diverse because 7 appears in it $$$1$$$ time and the number of distinct characters in it is $$$1$$$;
- string "77" is not diverse because 7 appears in it $$$2$$$ times and the number of distinct characters in it is $$$1$$$;
- string "1010" is diverse because both 0 and 1 appear in it $$$2$$$ times and the number of distinct characters in it is $$$2$$$;
- string "6668" is not diverse because 6 appears in it $$$3$$$ times and the number of distinct characters in it is $$$2$$$.

You are given a string $$$s$$$ of length $$$n$$$, consisting of only digits $$$0$$$ to $$$9$$$. Find how many of its $$$\frac{n(n+1)}{2}$$$ substrings are diverse.

A string $$$a$$$ is a substring of a string $$$b$$$ if $$$a$$$ can be obtained from $$$b$$$ by deletion of several (possibly, zero or all) characters from the beginning and several (possibly, zero or all) characters from the end.

Note that if the same diverse string appears in $$$s$$$ multiple times, each occurrence should be counted independently. For example, there are two diverse substrings in "77" both equal to "7", so the answer for the string "77" is $$$2$$$.

## Input Format
Each test contains multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 10^5$$$) — the length of the string $$$s$$$.

The second line of each test case contains a string $$$s$$$ of length $$$n$$$. It is guaranteed that all characters of $$$s$$$ are digits from $$$0$$$ to $$$9$$$.

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

## Output Format
For each test case print one integer — the number of diverse substrings of the given string $$$s$$$.

## Examples
```input
7
1
7
2
77
4
1010
5
01100
6
399996
5
23456
18
789987887987998798
```
```output
1
2
10
12
10
15
106
```

## Note
In the first test case, the diverse substring is "7".

In the second test case, the only diverse substring is "7", which appears twice, so the answer is $$$2$$$.

In the third test case, the diverse substrings are "0" ($$$2$$$ times), "01", "010", "1" ($$$2$$$ times), "10" ($$$2$$$ times), "101" and "1010".

In the fourth test case, the diverse substrings are "0" ($$$3$$$ times), "01", "011", "0110", "1" ($$$2$$$ times), "10", "100", "110" and "1100".

In the fifth test case, the diverse substrings are "3", "39", "399", "6", "9" ($$$4$$$ times), "96" and "996".

In the sixth test case, all $$$15$$$ non-empty substrings of "23456" are diverse.

Now solve the problem and return the code.