C. Хорошие подотрезки
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам задан массив $$$a_1, a_2, \dots , a_n$$$, состоящий из чисел от $$$0$$$ до $$$9$$$. Подотрезок этого массива $$$a_l, a_{l+1}, a_{l+2}, \dots , a_{r-1}, a_r$$$ хороший, если сумма чисел на этом подотрезке равна длине этого подотрезка ($$$\sum\limits_{i=l}^{r} a_i = r - l + 1$$$).

Например, если $$$a = [1, 2, 0]$$$, то есть $$$3$$$ хороших подотрезка: $$$a_{1 \dots 1} = [1], a_{2 \dots 3} = [2, 0]$$$ и $$$a_{1 \dots 3} = [1, 2, 0]$$$.

Посчитайте количество хороших подотрезков массива $$$a$$$.

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

Первая строка содержит целое число $$$t$$$ ($$$1 \le t \le 1000$$$) — количество наборов входных данных.

Первая строка каждого набора входных данных содержит целое число $$$n$$$ ($$$1 \le n \le 10^5$$$) — длина массива $$$a$$$.

Вторая строка каждого набора входных данных содержит $$$n$$$ десятичных цифр, где $$$i$$$-я цифра равна значению $$$a_i$$$.

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

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

На каждый набор входных данных выведите ответ — количество хороших подотрезков массива $$$a$$$.

Пример
Входные данные
3
3
120
5
11011
6
600005
Выходные данные
3
6
1
Примечание

Первый набор входных данных рассмотрен в условии.

Во втором наборе входных данных есть $$$6$$$ хороших подотрезков: $$$a_{1 \dots 1}$$$, $$$a_{2 \dots 2}$$$, $$$a_{1 \dots 2}$$$, $$$a_{4 \dots 4}$$$, $$$a_{5 \dots 5}$$$ и $$$a_{4 \dots 5}$$$.

В третьем наборе входных данных есть только один хороший подотрезок: $$$a_{2 \dots 6}$$$.