差异

题号：NC313185
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

$\hspace{15pt}$ 小苯有 $n$ 个长度为 $m$ ，仅由字符 $\texttt{0}$ 和 $\texttt{1}$ 组成的字符串 $s_1, s_2, \dots, s_n$ 。全部下标均从 $1$ 开始。

$\hspace{15pt}$ 定义两个字符串 $u$ 和 $v$ 的差异度为它们对应位置字符不同的数量，即：

$\displaystyle\text{diff}(u, v) = \Big\lvert\{k : u_k \neq v_k\}\Big\rvert = \sum_{k=1}^m [u_k \neq v_k]$

$\hspace{15pt}$ 对于第 $i$ 个字符串 $s_i$ ，小苯定义其邻居距离为 $s_i$ 与所有其他字符串的差异度之和：

$\displaystyle D_i = \sum_{j=1, j \neq i}^n \text{diff}(s_i, s_j)$

$\hspace{15pt}$ 现在，小苯每一次在求 $D_i$ 之前，都可以独立地对 $s_i$ 进行一次操作（当然也可以不操作）：选择当前字符串的一个区间 $[l_i, r_i]\ (1 \leqq l_i \leqq r_i \leqq m)$ ，然后将 $s_i$ 的第 $l_i$ 到第 $r_i$ 个字符进行 01 反置。

$\hspace{15pt}$ 你的任务就是对于每个 $i\left(1 \leqq i \leqq n\right)$ 求出：对 $s_i$ 进行最优操作后，能得到的最小邻居距离。

【名词解释】
$\hspace{15pt}$ 本题公式中的大括号代表艾弗森括号，具体地， $[P] = \begin{cases} 1 & \text{如果 } P \text{ 为真} \\ 0 & \text{如果 } P \text{ 为假} \end{cases}$ 。
$\hspace{15pt}$ 01 反置：同时将字符串中的 $\texttt{0}$ 变成 $\texttt{1}$ ， $\texttt{1}$ 变成 $\texttt{0}$ 。

输入描述:

每个测试文件包含多组测试数据。第一行输入一个整数  代表数据组数，每组测试数据描述如下：
第一行输入两个整数 ，表示字符串的数量、字符串长度。
此后  行，第  行输入一个长度为 ，仅由  和  组成的字符串 ，表示第  个字符串。
除此之外，保证单个测试文件的  之和不超过 。

输出描述:

对于每一组测试数据，一共  行，第  行输出一个整数，表示字符串  操作后的最小邻居距离。

示例1

输入

复制

输出

复制

2
2
4

备注:

在几乎全部的情况下，PyPy 的运行速度优于 Python，我们建议您选择对应版本的 PyPy 进行提交、而不是 Python。