在一次世界巡演之后,Vova 将自己困在了 $$$n \times m$$$ 矩阵中。该矩阵的行从上到下用从 $$$1$$$ 到 $$$n$$$ 的整数进行编号,列从左到右用从 $$$1$$$ 到 $$$m$$$ 的整数进行编号。单元格 $$$(i, j)$$$ 是 $$$1 \leq i \leq n$$$ 和 $$$1 \leq j \leq m$$$ 行 $$$i$$$ 和列 $$$j$$$ 的交叉点上的单元格。
该矩阵的一些单元格被障碍物阻挡,而所有其他单元格都是空的。 Vova 占据了其中一个空单元格。保证单元格 $$$(1, 1)$$$、$$$(1, m)$$$、$$$(n, 1)$$$、$$$(n, m)$$$(即矩阵的角点)被遮挡。
如果 Vova 共用一侧,则它们可以从一个空单元格移动到另一个空单元格。 Vova可以从矩阵边界上的任何空单元格逃逸矩阵;这些单元称为出口。
Vova 根据他可以用来逃离矩阵的出口数量定义了矩阵的类型:
- $$$1$$$-st类型:没有出口的矩阵,他可以用来逃脱。
- $$$2$$$-nd 类型:只有一个出口的矩阵,他可以用它来逃脱。
- $$$3$$$-rd 类型:具有多个(两个或更多)出口的矩阵,他可以使用它来逃脱。
在Vova开始移动之前,Misha可以制造更多障碍来阻挡更多细胞。但是,他无法改变矩阵的类型。 Misha 可以阻止的最大单元数是多少,以使矩阵类型保持不变?米莎无法阻挡沃娃当前所站立的牢房。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \leq t \leq 10\,000$$$)。测试用例的描述如下。
每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$3 \leq n,m \leq 1000$$$) — 矩阵的维度。
接下来的 $$$n$$$ 行包含矩阵的描述:其中第 $$$i$$$ ($$$1 \le i \le n$$$) 包含长度为 $$$m$$$ 的字符串,由字符“.”、“#”和“V”组成。第 $$$i$$$ 行的第 $$$j$$$ 字符描述矩阵的单元格 $$$(i, j)$$$。点“.”表示空单元格,尖号“#”表示被阻塞的单元格,字母“V”表示 Vova 最初所在的空单元格。
保证矩阵的角点被遮挡(矩阵描述的第一行和最后一行的第一个和最后一个字符是'#')。保证字母“V”在矩阵描述中只出现一次。
保证所有测试用例的 $$$n \cdot m$$$ 总和不超过 $$$1\,000\,000$$$。
输出
对于每个测试用例,输出一个整数——Misha 可能阻塞的最大单元数。
示例
输入 #1
8 4 4 #..# ..V. .... #..# 3 6 #.#### #....# ####V# 3 3 ### #V# ### 6 5 #.### #...# ###.# #V..# #.### ##..# 7 5 ##### #.V.# #.#.# #.#.# #.#.# #...# #.#.# 3 7 #.....# .#####. #...V.# 5 8 ####.### #..V#..# #...#..# #...##.# ###.#### 5 5 #...# ##.## ##V## ##.## #...#
输出 #1
9 0 0 3 4 10 12 5
注意
在第一个测试用例中,矩阵是 $$$3$$$-rd 类型。 Misha 可以在除单元格 $$$(1, 3)$$$、$$$(2, 3)$$$、$$$(2, 4)$$$ 之外的所有空单元格中创建障碍。这样的单元格有$$$9$$$,添加这样的障碍物不会改变矩阵的类型。
在第二个测试用例中,矩阵是 $$$3$$$-rd 类型。阻止任何单元格都会将矩阵类型更改为 $$$2$$$-nd:两个出口之一将变得不可用于 Vova。因此,答案是$$$0$$$。
在第三个测试用例中,矩阵是 $$$1$$$-st 类型。不存在空闲单元(除了 Vova 的单元),因此 Misha 无法阻止任何单元。
在第四个测试用例中,矩阵是 $$$2$$$-nd 类型。 Misha 可以在单元格 $$$(5, 2)$$$、$$$(6, 3)$$$、$$$(6, 4)$$$ 中创建 $$$3$$$ 障碍,而无需更改矩阵类型。
在第五个测试用例中,矩阵是 $$$3$$$-rd 类型。 Misha 可以在单元格中创建 $$$4$$$ 障碍 $$$(2, 2)$$$、$$$(3, 2)$$$、$$$(4, 2)$$$、$$$(5, 2)$$$ 或 $$$4$$$ 单元格障碍 $$$(2, 4)$$$、$$$(3, 4)$$$、$$$(4, 4)$$$, $$$(5, 4)$$$ 不改变矩阵的类型。