G. Гэнгста
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дана бинарная строка $$$s_1s_2 \ldots s_n$$$ длины $$$n$$$. Строка $$$s$$$ называется бинарной, если состоит только из нулей и единиц.

Для строки $$$p$$$ зададим функцию $$$f(p)$$$, равную наибольшему количеству вхождений какого-либо символа в строку $$$p$$$. Например, $$$f(00110) = 3$$$, $$$f(01) = 1$$$.

Вам нужно найти сумму $$$f(s_ls_{l+1} \ldots s_r)$$$ для всех пар $$$1 \leq l \leq r \leq n$$$.

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

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

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

Вторая строка каждого набора входных данных содержит строку длины $$$n$$$, состоящую из $$$0$$$ и $$$1$$$ — бинарную строку $$$s$$$.

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

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

Для каждого набора входных данных выведите сумму $$$f(s_ls_{l+1} \ldots s_r)$$$ для всех пар $$$1 \leq l \leq r \leq n$$$.

Пример
Входные данные
6
1
0
2
01
4
0110
6
110001
8
10011100
11
01011011100
Выходные данные
1
3
14
40
78
190
Примечание

В первом наборе входных данных у строки $$$s$$$ есть одна подстрока, и значение $$$f(0) = 1$$$.

Во втором наборе входных данных все подстроки строки $$$s$$$ равны $$$0$$$, $$$01$$$, $$$1$$$. И ответ равен $$$1 + 1 + 1 = 3$$$ соответственно.

В третьем наборе входных данных все подстроки строки $$$s$$$ равны $$$0$$$, $$$01$$$, $$$011$$$, $$$0110$$$, $$$1$$$, $$$11$$$, $$$110$$$, $$$1$$$, $$$10$$$, $$$0$$$. И ответ равен $$$1 + 1 + 2 + 2 + 1 + 2 + 2 + 1 + 1 + 1 = 14$$$ соответственно.