解题思路

先把题意抽象一下。

给定一个 $n \times m$ 的字符矩阵，每个位置是 'B' 或 'S'。

对于每一行，我们可以独立选择删除这一行最左侧的 $k$ 个字符，其中 $0 \le k \le m$。 要求删除后，整个矩阵中剩余的 'B' 和 'S' 数量相等。 目标是让删除的总字符数最少。

题目内容

有一个大小为 $n × m$ 的储物柜，格子里放着两种果酱：蓝莓酱（记作 $'B'$）和草莓酱（记作 $'S'$），他希望储物柜中两种果酱的数量相等。

对于储物柜的每一行，你都可以独立地选择移除其最左侧的 k 瓶果酱（$0 ≤ k ≤ m，k = 0$表示不移除该行的任何果酱）。

请你计算，最少需要拿走多少瓶果酱，才能使柜中剩余的 $'B'$与 $'S'$的数量相等。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数 $T(1 ≤ T ≤ 2 × 10^3)$表示测试组数。

对每组测试数据：

• 第一行输入两个整数 $n, m(1 ≤ n, m, n × m ≤ 2 × 10^3)$；
• 接下来 $n$ 行，每行一个长度为 $m$的仅由$'B'$ 与 $'S'$组成的字符串。

保证所有测试组中 $\sum(n × m) ≤ 5 × 10^3$。

输出描述

对于每组测试数据，输出一行，仅包含一个整数———为使$'b'$与$'S'$数量相等所需拿走的最少瓶数

样例1

输入

3
1 5
BSSSB
2 4
BSSB
SBBB
2 3
BBB
SSS

输出

3 
4 
0

说明

• 样例一：在第 $1$行拿走前缀长度$3$即可使总差值变为$0$，最少拿走$3$ 瓶。
• 样例二：在第$2$ 行拿走前缀长度$4(SBBB)$即可使总差值变为$0$，最少拿走 $4$ 瓶。
• 样例三：初始总计 $B=3, S=3$，差值已为$0$，无需拿走任何瓶，答案为$0$