311072: CF1930D1. Sum over all Substrings (Easy Version)

D1. Sum over all Substrings (Easy Version)time limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

This is the easy version of the problem. The only difference between the two versions is the constraint on $t$ and $n$. You can make hacks only if both versions of the problem are solved.

For a binary$^\dagger$ pattern $p$ and a binary string $q$, both of length $m$, $q$ is called $p$-good if for every $i$ ($1 \leq i \leq m$), there exist indices $l$ and $r$ such that:

• $1 \leq l \leq i \leq r \leq m$, and
• $p_i$ is a mode$^\ddagger$ of the string $q_l q_{l+1} \ldots q_{r}$.

For a pattern $p$, let $f(p)$ be the minimum possible number of $\mathtt{1}$s in a $p$-good binary string (of the same length as the pattern).

You are given a binary string $s$ of size $n$. Find $$\sum_{i=1}^{n} \sum_{j=i}^{n} f(s_i s_{i+1} \ldots s_j).$$ In other words, you need to sum the values of $f$ over all $\frac{n(n+1)}{2}$ substrings of $s$.

$^\dagger$ A binary pattern is a string that only consists of characters $\mathtt{0}$ and $\mathtt{1}$.

$^\ddagger$ Character $c$ is a mode of string $t$ of length $m$ if the number of occurrences of $c$ in $t$ is at least $\lceil \frac{m}{2} \rceil$. For example, $\mathtt{0}$ is a mode of $\mathtt{010}$, $\mathtt{1}$ is not a mode of $\mathtt{010}$, and both $\mathtt{0}$ and $\mathtt{1}$ are modes of $\mathtt{011010}$.

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 500$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($1 \le n \le 100$) — the length of the binary string $s$.

The second line of each test case contains a binary string $s$ of length $n$ consisting of only characters $\mathtt{0}$ and $\mathtt{1}$.

It is guaranteed that the sum of $n^2$ over all test cases does not exceed $10^4$.

Output

For each test case, output the sum of values of $f$ over all substrings of $s$.

ExampleInput

4
1
1
2
10
5
00000
20
11110110000000111111

Output

1
2
0
346

Note

In the first test case, the only $\mathtt{1}$-good string is $\mathtt{1}$. Thus, $f(\mathtt{1})=1$.

In the second test case, $f(\mathtt{10})=1$ because $\mathtt{01}$ is $\mathtt{10}$-good, and $\mathtt{00}$ is not $\mathtt{10}$-good. Thus, the answer is $f(\mathtt{1})+f(\mathtt{10})+f(\mathtt{0}) = 1 + 1 + 0 = 2$.

In the third test case, $f$ equals to $0$ for all $1 \leq i \leq j \leq 5$. Thus, the answer is $0$.

题目大意：

这是一个关于二进制字符串的题目，分为简单和困难两个版本，两者的区别仅在于限制条件$t$和$n$的不同。只有当两个版本的问题都解决后，才能进行黑客攻击。

对于一个长度为$m$的二进制模式$p$和一个二进制字符串$q$，如果对于任意的$i$（$1 \leq i \leq m$），都存在下标$l$和$r$满足以下条件：

1. $1 \leq l \leq i \leq r \leq m$，并且
2. $p_i$是字符串$q_l q_{l+1} \ldots q_{r}$的众数。

那么，称$q$是$p$-好的。对于模式$p$，记$f(p)$为满足上述条件的$p$-好二进制字符串中$\mathtt{1}$的最小可能数量。

给定一个长度为$n$的二进制字符串$s$，需要计算

\[
\sum_{i=1}^{n} \sum_{j=i}^{n} f(s_i s_{i+1} \ldots s_j).
\]

即对所有$\frac{n(n+1)}{2}$个$s$的子字符串求$f$的值并求和。

输入输出数据格式：

输入：
- 第一行包含一个整数$t$（$1 \le t \le 500$），表示测试用例的数量。
- 每个测试用例包含两行：
- 第一行包含一个整数$n$（$1 \le n \le 100$），表示二进制字符串$s$的长度。
- 第二行包含一个长度为$n$的二进制字符串$s$，只包含字符$\mathtt{0}$和$\mathtt{1}$。
- 保证所有测试用例的$n^2$之和不超过$10^4$。

输出：
- 对于每个测试用例，输出一个整数，表示所有子字符串的$f$值之和。

示例输入输出：

输入：
```
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$。
- 在第三个测试用例中，对于所有$1 \leq i \leq j \leq 5$，$f$的值都是$0$。因此，答案是$0$。题目大意： 这是一个关于二进制字符串的题目，分为简单和困难两个版本，两者的区别仅在于限制条件$t$和$n$的不同。只有当两个版本的问题都解决后，才能进行黑客攻击。 对于一个长度为$m$的二进制模式$p$和一个二进制字符串$q$，如果对于任意的$i$（$1 \leq i \leq m$），都存在下标$l$和$r$满足以下条件： 1. $1 \leq l \leq i \leq r \leq m$，并且 2. $p_i$是字符串$q_l q_{l+1} \ldots q_{r}$的众数。 那么，称$q$是$p$-好的。对于模式$p$，记$f(p)$为满足上述条件的$p$-好二进制字符串中$\mathtt{1}$的最小可能数量。 给定一个长度为$n$的二进制字符串$s$，需要计算 \[ \sum_{i=1}^{n} \sum_{j=i}^{n} f(s_i s_{i+1} \ldots s_j). \] 即对所有$\frac{n(n+1)}{2}$个$s$的子字符串求$f$的值并求和。 输入输出数据格式： 输入： - 第一行包含一个整数$t$（$1 \le t \le 500$），表示测试用例的数量。 - 每个测试用例包含两行： - 第一行包含一个整数$n$（$1 \le n \le 100$），表示二进制字符串$s$的长度。 - 第二行包含一个长度为$n$的二进制字符串$s$，只包含字符$\mathtt{0}$和$\mathtt{1}$。 - 保证所有测试用例的$n^2$之和不超过$10^4$。 输出： - 对于每个测试用例，输出一个整数，表示所有子字符串的$f$值之和。 示例输入输出： 输入： ``` 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$。 - 在第三个测试用例中，对于所有$1 \leq i \leq j \leq 5$，$f$的值都是$0$。因此，答案是$0$。