CF1898F.Vova Escapes the Matrix

Following a world tour, Vova got himself trapped inside an $n \times m$ matrix. Rows of this matrix are numbered by integers from $1$ to $n$ from top to bottom, and the columns are numbered by integers from $1$ to $m$ from left to right. The cell $(i, j)$ is the cell on the intersection of row $i$ and column $j$ for $1 \leq i \leq n$ and $1 \leq j \leq m$.

Some cells of this matrix are blocked by obstacles, while all other cells are empty. Vova occupies one of the empty cells. It is guaranteed that cells $(1, 1)$, $(1, m)$, $(n, 1)$, $(n, m)$ (that is, corners of the matrix) are blocked.

Vova can move from one empty cell to another empty cell if they share a side. Vova can escape the matrix from any empty cell on the boundary of the matrix; these cells are called exits.

Vova defines the type of the matrix based on the number of exits he can use to escape the matrix:

• The $1$-st type: matrices with no exits he can use to escape.
• The $2$-nd type: matrices with exactly one exit he can use to escape.
• The $3$-rd type: matrices with multiple (two or more) exits he can use to escape.

Before Vova starts moving, Misha can create more obstacles to block more cells. However, he cannot change the type of the matrix. What is the maximum number of cells Misha can block, so that the type of the matrix remains the same? Misha cannot block the cell Vova is currently standing on.

在一场世界巡演之后，沃瓦被困在一个 $n \times m$ 的矩阵中。该矩阵的行从上到下依次编号为 $1$ 到 $n$，列从左到右依次编号为 $1$ 到 $m$。对于 $1 \leq i \leq n$ 且 $1 \leq j \leq m$，单元格 $(i, j)$ 表示第 $i$ 行与第 $j$ 列相交处的单元格。

该矩阵中某些单元格被障碍物封锁，其余单元格均为空。沃瓦位于其中一个空单元格上。保证单元格 $(1, 1)$、$(1, m)$、$(n, 1)$、$(n, m)$（即矩阵的四个角）均被封锁。

沃瓦可以从一个空单元格移动到另一个空单元格，当且仅当这两个单元格共享一条边（即上下左右相邻）。沃瓦可以从矩阵边界上的任意一个空单元格逃出矩阵；这些单元格称为“出口”。

沃瓦根据他可用于逃出矩阵的出口数量，将矩阵定义为以下三种类型之一：

• 第 $1$ 类：不存在任何可用于逃出的出口；
• 第 $2$ 类：恰好存在一个可用于逃出的出口；
• 第 $3$ 类：存在多个（两个或更多）可用于逃出的出口。

在沃瓦开始移动之前，米沙可以额外设置障碍物以封锁更多单元格。但米沙不得改变矩阵的类型。那么，在保持矩阵类型不变的前提下，米沙最多能封锁多少个单元格？注意：米沙不能封锁沃瓦当前所处的单元格。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \leq t \leq 10\,000$). The description of test cases follows.

The first line of each test case contains two integers $n$ and $m$ ($3 \leq n,m \leq 1000$) — the dimensions of the matrix.

The next $n$ lines contain the description of the matrix: the $i$-th ($1 \le i \le n$) of them contains a string of length $m$, consisting of characters '.', '#', and 'V'. The $j$-th character of the $i$-th line describes the cell $(i, j)$ of the matrix. The dot '.' denotes an empty cell, the sharp '#' denotes a blocked cell, and the letter 'V' denotes an empty cell where Vova initially is.

It is guaranteed that the corners of the matrix are blocked (the first and the last characters of the first and the last lines of the matrix description are '#'). It is guaranteed that the letter 'V' appears in the matrix description exactly once.

It is guaranteed that the sum of $n \cdot m$ over all test cases does not exceed $1\,000\,000$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $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$。

For each test case, output a single integer — the maximum number of cells Misha may block.

对于每个测试用例，输出一个整数——Misha 最多可以封锁的格子数量。

In the first test case, the matrix is of the $3$-rd type. Misha can create obstacles in all empty cells except the cells $(1, 3)$, $(2, 3)$, $(2, 4)$. There are $9$ such cells, and adding such obstacles does not change the type of the matrix.

In the second test case, the matrix is of the $3$-rd type. Blocking any cell changes the matrix type to the $2$-nd: one of the two exits will become unavailable for Vova. Thus, the answer is $0$.

In the third test case, the matrix is of the $1$-st type. No free cell exists (besides Vova's), so Misha cannot block any cell.

In the fourth test case, the matrix is of the $2$-nd type. Misha can create $3$ obstacles in cells $(5, 2)$, $(6, 3)$, $(6, 4)$ without changing the type of the matrix.

In the fifth test case, the matrix is of the $3$-rd type. Misha can create $4$ obstacles in cells $(2, 2)$, $(3, 2)$, $(4, 2)$, $(5, 2)$ or $4$ obstacles in cells $(2, 4)$, $(3, 4)$, $(4, 4)$, $(5, 4)$ without changing the type of the matrix.

在第一个测试用例中，该矩阵属于第 $3$ 类。米沙可以在所有空单元格（除 $(1, 3)$、$(2, 3)$、$(2, 4)$ 外）放置障碍物。这样的单元格共有 $9$ 个，且在这些位置添加障碍物不会改变矩阵的类型。

在第二个测试用例中，该矩阵属于第 $3$ 类。封锁任意一个单元格都会使矩阵类型变为第 $2$ 类：沃瓦将无法使用两个出口中的一个。因此，答案为 $0$。

在第三个测试用例中，该矩阵属于第 $1$ 类。除沃瓦所在单元格外，不存在其他空单元格，因此米沙无法封锁任何单元格。

在第四个测试用例中，该矩阵属于第 $2$ 类。米沙可在单元格 $(5, 2)$、$(6, 3)$、$(6, 4)$ 放置 $3$ 个障碍物，且不改变矩阵的类型。

在第五个测试用例中，该矩阵属于第 $3$ 类。米沙可在单元格 $(2, 2)$、$(3, 2)$、$(4, 2)$、$(5, 2)$ 放置 $4$ 个障碍物，或在单元格 $(2, 4)$、$(3, 4)$、$(4, 4)$、$(5, 4)$ 放置 $4$ 个障碍物，均不会改变矩阵的类型。