SP1022 ANGELS - Angels and Devils

公元 21546 年，人类数量急剧增长（具体数据可能令你震惊），导致土地极其昂贵。由于空间的稀缺，天堂和地狱被建在同一个区域。这个区域可以用一个 **X** × **Y** 的网格来表示。网格中的某些方格被恶魔占领（即属于地狱），其余方格则属于全能神。这些方格上建有房间，房间的墙壁是透明玻璃做成。然而，一些天堂房间已经被天使占用，为保障安全，这些房间有不透明的混凝土墙。 最近，在一场比赛中，许多战士丧生。现在战斗不再被视为残酷，因此所有这些战士都应该在天堂获得安置。然而，由于空间有限，并非所有战士都能获得房间。并且，由于他们之间的仇恨，一名战士不能安置在一个能看到其他战士的房间里。战士只能看到正北、正南、正东和正西的方向，无法作为斜向观察。 请计算能够为战士安排进天堂的最大房间数目。

输入的第一行为一个整数 **t**，表示测试用例数量。接下来有 **t** 个测试用例。 每个测试用例第一行包含两个整数 **X** 和 **Y**，以空格隔开。接下来的 **X** 行中，每行包含 **Y** 个字母，字母之间用空格隔开。第 **i** 行第 **j** 列的字母含义如下： 1. "H"：位置 (i, j) 的房间是空的天堂房间。 2. "A"：位置 (i, j) 的房间是被天使占用的天堂房间，不透明。 3. "D"：位置 (i, j) 的房间属于地狱。

对于每个测试用例，输出一行，表示战士能够安排入驻的最大天堂房间的数量。

- 测试用例数量满足：\(1 \le t \le 10\) - 网格大小满足：\(1 \le X, Y \le 300\) **本翻译由 AI 自动生成**