B. Разнообразные подстроки
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Непустая строка из цифр является разнообразной, если количество вхождений каждого символа в неё не превосходит количество различных символов в ней.

Например,

  • строка «7» разнообразная, так как 7 встречается в ней $$$1$$$ раз, и количество различных символов в ней равно $$$1$$$;
  • строка «77» не является разнообразной, так как 7 встречается в ней $$$2$$$ раза, а количество различных символов в ней равно $$$1$$$;
  • строка «1010» разнообразная, так как 0 и 1 встречаются в ней по $$$2$$$ раза, и количество различных символов в ней равно $$$2$$$;
  • строка «6668» не является разнообразной, так как 6 встречается в ней $$$3$$$ раза, а количество различных символов в ней равно $$$2$$$.

Вам дана строка $$$s$$$ длины $$$n$$$, состоящая из цифр от $$$0$$$ до $$$9$$$. Найдите, сколько из ее $$$\frac{n(n+1)}{2}$$$ подстрок являются разнообразными.

Строка $$$a$$$ является подстрокой $$$b$$$, если $$$a$$$ может быть получена из $$$b$$$ удалением нескольких (возможно, ни одного или всех) символов из начала и нескольких (возможно, ни одного или всех) символов из конца.

Обратите внимание, что если некоторая разнообразная строка встречается в $$$s$$$ несколько раз, то каждое её вхождение должно быть подсчитано независимо. Например, в строке «77» есть две разнообразных подстроки, равных «7», поэтому ответ для строки «77» равен $$$2$$$.

Входные данные

В первой строке задано одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следуют описания этих наборов.

В первой строке дано одно число $$$n$$$ ($$$1 \le n \le 10^5$$$) — длина строки $$$s$$$.

Во второй строке дана строка $$$s$$$ длины $$$n$$$. Гарантируется, что $$$s$$$ состоит только из цифр от $$$0$$$ до $$$9$$$.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$10^5$$$.

Выходные данные

Для каждого набора входных данных выведите одно число: количество разнообразных подстрок строки $$$s$$$.

Пример
Входные данные
7
1
7
2
77
4
1010
5
01100
6
399996
5
23456
18
789987887987998798
Выходные данные
1
2
10
12
10
15
106
Примечание

В первом наборе входных данных подстрока «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».

В шестом наборе входных данных все $$$15$$$ непустых подстрок строки «23456» являются разнообразными.