所有子串的和（困难版）

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

题目描述

对于一个二进制模式 $p$ 和一个同长度二进制串 $q$，若对 $p$ 的每个位置 $i$，都能找到包含 $i$ 的一个区间，使得 $p_i$ 是 $q$ 在该区间中的众数，则称 $q$ 是 $p$-good 的。一个字符在某串中出现次数不少于串长的一半（向上取整）时，它是该串的众数。

记 $f(p)$ 为所有 $p$-good 二进制串中字符 1 数量的最小值。

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

输入格式

第一行一个整数 $t$，表示测试用例数。

每组测试先输入整数 $n$，下一行输入长度为 $n$、仅含 0 和 1 的字符串 $s$。

保证 $1\le t\le 10^5$，$1\le n\le 10^6$，且所有测试用例的 $n$ 之和不超过 $10^6$。

输出格式

对每组测试输出一个整数，表示答案。

样例输入

4
1
1
2
10
5
00000
20
11110110000000111111

样例输出

1
2
0
346

数据范围

对于所有数据，保证 $1\le t\le 10^5$，$1\le n\le 10^6$，且所有测试用例的 $n$ 之和不超过 $10^6$。