所有子串的贡献和（简单版）

• 时间限制：2 秒
• 内存限制：256 MiB

题目描述

对于长度同为 $m$ 的二进制模式 $p$ 与二进制字符串 $q$，若对每个位置 $i$，都存在一个包含 $i$ 的区间 $[l,r]$，使字符 $p_i$ 是 $q_lq_{l+1}\ldots q_r$ 的众数，则称 $q$ 是 $p$-good 的。

字符 $c$ 是一个字符串的众数，当且仅当 $c$ 的出现次数不少于该字符串长度的一半（向上取整）。因此在偶数长度字符串中，两个字符可以同时是众数。

定义 $f(p)$ 为所有 $p$-good 字符串 $q$ 中字符 1 的最少数量。

给定长度为 $n$ 的二进制字符串 $s$，求

输入格式

第一行包含测试组数 $t$（$1\le t\le500$）。

每组数据第一行包含 $n$（$1\le n\le100$），第二行包含长度为 $n$、仅由 0 和 1 构成的字符串 $s$。

保证所有测试组中 $n^2$ 的总和不超过 $10^4$。

输出格式

对每组数据输出一个整数，表示所有子串的 $f$ 值之和。

样例输入 1

4
1
1
2
10
5
00000
20
11110110000000111111

样例输出 1

1
2
0
346

数据范围

对于所有数据，$1\le t\le500$，$1\le n\le100$，且所有测试组中 $n^2$ 的总和不超过 $10^4$。