D1. Сумма по всем подстрокам (простая версия)
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это простая версия задачи. Единственное отличие между версиями заключается в ограничениях на $$$t$$$ и $$$n$$$. Вы можете делать взломы только тогда, когда обе версии задачи решены.

Для бинарного$$$^\dagger$$$ шаблона $$$p$$$ и бинарной строки $$$q$$$ одинаковой длины $$$m$$$, скажем, что строка $$$q$$$ называется $$$p$$$-хорошей, если для каждого $$$i$$$ ($$$1 \leq i \leq m$$$) существуют индексы $$$l$$$ и $$$r$$$ такие, что:

  • $$$1 \leq l \leq i \leq r \leq m$$$, и
  • $$$p_i$$$ является модой$$$^\ddagger$$$ строки $$$q_l q_{l+1} \ldots q_{r}$$$.

Для шаблона $$$p$$$ определим $$$f(p)$$$ как минимально возможное количество $$$\mathtt{1}$$$ в $$$p$$$-хорошей бинарной строке (такой же длины, как и шаблон).

Вам дана бинарная строка $$$s$$$ длины $$$n$$$. Найдите $$$$$$\sum_{i=1}^{n} \sum_{j=i}^{n} f(s_i s_{i+1} \ldots s_j).$$$$$$ Другими словами, вам нужно просуммировать значения $$$f$$$ по всем $$$\frac{n(n+1)}{2}$$$ подстрокам $$$s$$$.

$$$^\dagger$$$ Бинарный шаблон — это строка, состоящая только из символов $$$\mathtt{0}$$$ и $$$\mathtt{1}$$$.

$$$^\ddagger$$$ Символ $$$c$$$ является модой строки $$$t$$$ длины $$$m$$$, если число вхождений $$$c$$$ в $$$t$$$ не меньше $$$\lceil \frac{m}{2} \rceil$$$. Например, $$$\mathtt{0}$$$ является модой $$$\mathtt{010}$$$, $$$\mathtt{1}$$$ не является модой $$$\mathtt{010}$$$, и оба символа $$$\mathtt{0}$$$ и $$$\mathtt{1}$$$ являются модами $$$\mathtt{011010}$$$.

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

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

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

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

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

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

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

Пример
Входные данные
4
1
1
2
10
5
00000
20
11110110000000111111
Выходные данные
1
2
0
346
Примечание

В первом наборе входных данных единственной $$$\mathtt{1}$$$-хорошей строкой является $$$\mathtt{1}$$$. Таким образом, $$$f(\mathtt{1})=1$$$.

Во втором наборе входных данных $$$f(\mathtt{10})=1$$$, так как $$$\mathtt{01}$$$ является $$$\mathtt{10}$$$-хорошей, а $$$\mathtt{00}$$$ не является $$$\mathtt{10}$$$-хорошей. Таким образом, ответ равен $$$f(\mathtt{1})+f(\mathtt{10})+f(\mathtt{0}) = 1 + 1 + 0 = 2$$$.

В третьем наборе входных данных $$$f$$$ равна $$$0$$$ для всех $$$1 \leq i \leq j \leq 5$$$. Таким образом, ответ равен $$$0$$$.