B. Diverse Substrings

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

Each test contains multiple test cases. The first line contains a single integer $t$ $(1 \leq t \leq {10}^{4})$ — the number of test cases.

The first line of each test case contains a single integer $n$ $(1 \leq n \leq {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

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

Example

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.

解题思路

　　这题其实很简单。比赛的时候一直想着用减法来求出答案，就是先找到所有不满足条件的子串，然后用总的子串数量减去不满足条件的子串数量就是答案，然后发现这种做法特别麻烦，需要讨论的情况很多。跳到这个坑就出不来，一直想着怎么用这种方法去做，而不去想别的方法。

　　其实只要发现关键的条件，最多只有$10$个不同的字符，这意味着满足条件的子串长度不会超过$100$，因为如果子串的长度超过$100$，那么必然会存在某个字符的出现频率会超过$10$，而最多只有$10$个不同的字符。

　　接下来暴力枚举就好了，直接把长度不超过$100$的子串都枚举出来，然后判断是否满足条件。

　　时间复杂度为$O(n \cdot 100)$，计算量是${10}^{7}$级别。

　　AC代码如下：

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 const int N = 1e5 + 10;
 5 
 6 char str[N];
 7 
 8 void solve() {
 9     int n;
10     scanf("%d %s", &n, str);
11     int ret = 0;
12     for (int i = 0; i < n; i++) {    // 枚举子串左端点
13         int cnt[10] = {0}, maxv = 0, s = 0;
14         for (int j = i; j < n && j < i + 100; j++) {    // 枚举子串右端点，且子串的长度不超过100
15             int t = str[j] - '0';
16             maxv = max(maxv, ++cnt[t]);
17             if (cnt[t] == 1) s++;
18             if (maxv <= s) ret++;
19         }
20     }
21     printf("%d\n", ret);
22 }
23 
24 int main() {
25     int t;
26     scanf("%d", &t);
27     while (t--) {
28         solve();
29     }
30     
31     return 0;
32 }

参考资料

　　Codeforces Round #833 (Div. 2) Editorial：https://codeforces.com/blog/entry/108319