#1234. 阅览室

我们有一个图书馆。 图书馆是一个矩形，长为 $H$ 米，宽为 $W$ 米。 我们可以想象它被划分为单位正方形的单元格。 网格的行和列从零开始编号。 第 $i$ 行和第$j$ 列中的单元格表示为$(i,j)$。

图书馆场周围有一堵墙。 更准确地说，图书馆最外层的单位正方形的边缘都是墙。 此外，当前使用隔板隔开了成对的单元格对之间的某些内部边界。 每堵墙长1米，将它们水平或垂直放置在两个单元之间。

隔板的初始位置在一个长度 $2 * H + 1$ 的宽度 $2 * W + 1$ 的字符串矩阵中给出，如下所示。

+-+-+-+-+
|.|.....|
+.+-+-+-+
|.|.|...|
+-+-+.+.+
|.|.|...|
+-+.+.+-+
|...|...|
+-+-+-+-+

这是H = 4，W = 4的一个示例。单元格的顶点表示为'+'，垂直隔板和墙壁表示为'|'，水平隔板和墙壁表示为'-'，其他地方为'.'字符。

围墙和隔板将图书馆划分为一个或多个连通区域。我们将这些区域称为“阅览室”。

如果区域的形状为空矩形，则该区域可用。也就是说，可用区域的边界必须完全被墙壁和隔板覆盖，并且区域内不能有隔板。

我们有两个目标：

• 我们的主要目标是不浪费任何空间。所有单元格都必须用上且所有区域都必须可用。

• 我们的次要目标是必须最大化阅览室的数量。

• 我们唯一可以进行的更改操作是，我们可以移除若干块隔板（可以不移除或全部移除）。

在满足所有区域必须可用的前提下，计算并输出我们可能在给定图书馆内创建的最大阅览室数。

$$T \\ Case_1 \\ Case_2 \\ \ldots \\ Case_T$$

每个$Case$的格式如下

$$H\ W \\ S_1 \\ \ldots \\ S_{H*2+1}$$

每行一个整数，代表答案。

$T \le 1000, H*W \le 500$

使得 $H*W>100$ 的组数小于20