题目内容

在一个自动化仓库中，有 $n$ 排货架，每排有 $m$ 个货位，存放着两种不同规格的零件，分别标记为 'B' 和 'S'。管理员希望调整库存，使得仓库中两种零件的总数相同。对于每一排，他可以从最左侧开始移除连续若干个货位上的零件，也可以不移除任何零件（即移除 0 个）。

你需要计算，最少总共需要移除多少个零件，才能使得剩余零件中 'B' 的数量与 'S' 的数量相等。

约束：货架的排数 $n$ 和每排货位数 $m$ 满足 $1 \le n, m$ 且 $n \times m \le 2 \times 10^3$。所有测试数据中 $n \times m$ 的总和不超过 $5 \times 10^3$。测试组数 $T$ 满足 $1 \le T \le 2 \times 10^3$。

输入描述

第一行包含一个整数 $T$，表示测试数据组数。

对于每组测试数据：

• 第一行包含两个整数 $n$ 和 $m$，分别表示货架的排数和每排的货位数。
• 接下来 $n$ 行，每行包含一个长度为 $m$ 的字符串，仅由字符 'B' 和 'S' 组成，依次表示该排货架上零件的分布情况。

输出描述

对于每组测试数据，输出一行一个整数，表示最少需要移除的零件总数。

样例1

输入

1
1 1
B

输出

1

说明

只有 $1$ 排 $1$ 个零件 B，初始 B 数量为 1，S 数量为 0，差值 $D = 1$。 可选择删除 $0$ 个（差值为 $0$）或删除 $1$ 个（差值为 $+1$）。要让删除部分差值等于 $D=1$，必须移除该零件，最少移除 1 个。

样例2

输入

1
1 2
BS

输出

0

说明

只有 $1$ 排 $2$ 个零件，序列为 BS。初始 B 数量 1，S 数量 1，差值 $D=0$。 不需要移除任何零件即可使剩余两种数量相等，答案为 0。

样例3

输入

2
2 2
BB
BS
1 3
SSB

输出

2
1

说明

第一组数据：$2$ 排 $2$ 列，第一行 BB，第二行 BS。总 B 数量 $3$，总 S 数量 $1$，差值 $D = 2$。 第一行前缀方案：长度 $0$ 差值 $0$，长度 $1$ 差值 $+1$，长度 $2$ 差值 $+2$。保留每个差值的最小代价（删除长度）：$\Delta=0$ 代价 $0$，$\Delta=+1$ 代价 $1$，$\Delta=+2$ 代价 $2$。 第二行前缀：$0$ 长度差值 $0$，长度 $1$（B）差值 $+1$ 代价 $1$，长度 $2$（BS）差值 $0$ 代价 $2$（不如 $0$ 代价 $0$）。保留 $\Delta=0$ 代价 $0$，$\Delta=+1$ 代价 $1$。 需要删除部分总差值达到 $D=2$。组合：第一行选 $\Delta=+2$（代价 $2$），第二行选 $\Delta=0$（代价 $0$），总代价 $2$；或者两行都选 $\Delta=+1$（代价 $1+1=2$）。最小总代价为 $2$。

第二组数据：$1$ 排 $3$ 列，序列 SSB。总 B $1$，总 S $2$，差值 $D = -1$。 前缀方案：长度 $0$ 差值 $0$，长度 $1$（S）差值 $-1$ 代价 $1$，长度 $2$（SS）差值 $-2$ 代价 $2$，长度 $3$（SSB）差值 $-1$ 代价 $3$（不如长度 $1$）。保留 $\Delta=0$ 代价 $0$，$\Delta=-1$ 代价 $1$，$\Delta=-2$ 代价 $2$。 要达到 $D=-1$，选 $\Delta=-1$ 代价 $1$，最少移除 1 个零件。