[Solution] Diverse Substrings Codeforces Solution

B. Diverse Substrings

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

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

You are given a string 𝑠$s$ of length 𝑛$n$, consisting of only digits 0$0$ to 9$9$. Find how many of its 𝑛(𝑛+1)2$\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$2$.

Input

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

The first line of each test case contains a single integer 𝑛$n$ (1≤𝑛≤105$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$0$ to 9$9$.

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

Output

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

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

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

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

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

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