CF1748B.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$.

一个非空的数字字符串被称为“多样化的”，当且仅当其中每个字符的出现次数均不超过该字符串中不同字符的个数。

例如：

• 字符串 "7" 是多样化的，因为字符 7 在其中出现了 $1$ 次，而该字符串中不同字符的个数为 $1$；
• 字符串 "77" 不是多样化的，因为字符 7 在其中出现了 $2$ 次，而该字符串中不同字符的个数为 $1$；
• 字符串 "1010" 是多样化的，因为字符 0 和 1 在其中均出现了 $2$ 次，而该字符串中不同字符的个数为 $2$；
• 字符串 "6668" 不是多样化的，因为字符 6 在其中出现了 $3$ 次，而该字符串中不同字符的个数为 $2$。

给定一个长度为 $n$ 的字符串 $s$，它仅由数字 0 到 9 组成。请计算其 $\frac{n(n+1)}{2}$ 个子串中有多少个是多样化的。

若字符串 $a$ 可通过从字符串 $b$ 的开头删除若干（可能为零或全部）字符、并从结尾删除若干（可能为零或全部）字符而得到，则称 $a$ 是 $b$ 的一个子串。

注意：若同一个多样化的字符串在 $s$ 中多次出现，则每次出现都应被独立计数。例如，在字符串 "77" 中有两个多样化的子串，均为 "7"，因此字符串 "77" 的答案为 $2$。

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$.

每个测试包含多个测试用例。第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 10^5$），表示字符串 $s$ 的长度。

每个测试用例的第二行包含一个长度为 $n$ 的字符串 $s$。保证 $s$ 中的所有字符均为数字，取值范围为 $0$ 到 $9$。

保证所有测试用例的 $n$ 之和不超过 $10^5$。

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

对于每个测试用例，输出一个整数——字符串 $s$ 的不同子串的数量。

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.

在第一个测试用例中，多样子串为 "7"。

在第二个测试用例中，唯一的多样子串是 "7"，它出现了两次，因此答案为 $2$。

在第三个测试用例中，多样子串包括 "0"（出现 $2$ 次）、"01"、"010"、"1"（出现 $2$ 次）、"10"（出现 $2$ 次）、"101" 和 "1010"。

在第四个测试用例中，多样子串包括 "0"（出现 $3$ 次）、"01"、"011"、"0110"、"1"（出现 $2$ 次）、"10"、"100"、"110" 和 "1100"。

在第五个测试用例中，多样子串包括 "3"、"39"、"399"、"6"、"9"（出现 $4$ 次）、"96" 和 "996"。

在第六个测试用例中，字符串 "23456" 的全部 $15$ 个非空子串均为多样子串。