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

Назовем бинарную строку $$$T$$$ длины $$$m$$$, индексированную от $$$1$$$ до $$$m$$$ параноидальной, если мы можем получить строку длины $$$1$$$, выполнив следующие два вида операций $$$m-1$$$ раз в любом порядке:

  • Выберите любую подстроку $$$T$$$, которая равна 01, и замените ее на 1.
  • Выберите любую подстроку $$$T$$$, которая равна 10, а затем замените ее на 0.

    Например, если $$$T = $$$ 001, мы можем выбрать подстроку $$$[T_2T_3]$$$ и выполнить первую операцию. Таким образом, мы получим $$$T = $$$ 01 в качестве новой строки.

Вам дана бинарная строка $$$S$$$ длины $$$n$$$, индексированная от $$$1$$$ до $$$n$$$. Найдите количество пар целых чисел $$$(l, r)$$$ с $$$1 \le l \le r \le n$$$ таких, что $$$S[l \ldots r]$$$ (подстрока $$$S$$$ от $$$l$$$ до $$$r$$$) является параноидальной строкой.

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

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

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

Вторая строка каждого набора входных данных содержит бинарную строку $$$S$$$ из $$$n$$$ символов $$$S_1S_2 \ldots S_n$$$. ($$$S_i = $$$ 0 или $$$S_i = $$$ 1 для каждого $$$1 \le i \le n$$$).

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

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

Для каждого набора входных данных выведите количество пар целых чисел $$$(l, r)$$$ с $$$1 \le l \le r \le n$$$ таких, что $$$S[l \ldots r]$$$ (подстрока $$$S$$$ от $$$l$$$ до $$$r$$$) является параноидальной строкой.

Пример
Входные данные
5
1
1
2
01
3
100
4
1001
5
11111
Выходные данные
1
3
4
8
5
Примечание

В первом примере $$$S$$$ уже имеет длину $$$1$$$ и нет нужды ни в каких операциях.

Во втором примере все подстроки $$$S$$$ являются параноидальными. Для всей строки достаточно выполнить первую операцию.

В третьем примере все подстроки $$$S$$$ являются параноидальными, кроме $$$[S_2S_3]$$$, потому что мы не можем выполнить над ней никаких операций, и $$$[S_1S_2S_3]$$$ (всей строки).