310846: CF1898F. Vova Escapes the Matrix

F. Vova Escapes the Matrixtime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

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.

Input

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$.

Output

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

ExampleInput

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##
##.##
#...#

Output

9
0
0
3
4
10
12
5

Note

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.

题目大意：
Vova被困在一个n*m的矩阵中，矩阵的行从1到n从上到下编号，列从1到m从左到右编号。矩阵的一些单元格被障碍物阻挡，其余单元格为空。Vova占据一个空单元格。保证单元格(1,1)、(1,m)、(n,1)、(n,m)（即矩阵的角）被阻挡。Vova可以从一个空单元格移动到另一个与之共享边的空单元格。Vova可以从矩阵的任何空边界单元格逃脱，这些单元格称为出口。根据Vova可以用来逃脱矩阵的出口数量，Vova定义了矩阵的类型：
- 第1类：没有出口可以逃脱的矩阵。
- 第2类：恰好有一个出口可以逃脱的矩阵。
- 第3类：有两个或更多出口可以逃脱的矩阵。

在Vova开始移动之前，Misha可以创建更多障碍物来阻挡更多单元格，但他不能改变矩阵的类型。Misha最多可以阻挡多少个单元格，同时保持矩阵类型不变？Misha不能阻挡Vova当前所在的单元格。

输入输出数据格式：
每个测试用例包含多个测试案例。第一行包含测试案例的数量t(1≤t≤10,000)。接下来是每个测试案例的描述。
每个测试案例的第一行包含两个整数n和m(3≤n,m≤1000)——矩阵的维度。
接下来的n行包含矩阵的描述：第i行(1≤i≤n)包含一个长度为m的字符串，由字符'.'、'#'和'V'组成。第i行的第j个字符描述单元格(i,j)。点'.'表示空单元格，井号'#'表示被阻挡的单元格，字母'V'表示Vova最初所在的空单元格。
保证矩阵的角被阻挡（矩阵描述的第一行和最后一行的第一个和最后一个字符是'#'）。保证字母'V'在矩阵描述中恰好出现一次。
保证所有测试案例的n*m之和不超过1,000,000。
对于每个测试案例，输出一个整数——Misha可以阻挡的最大单元格数。题目大意： Vova被困在一个n*m的矩阵中，矩阵的行从1到n从上到下编号，列从1到m从左到右编号。矩阵的一些单元格被障碍物阻挡，其余单元格为空。Vova占据一个空单元格。保证单元格(1,1)、(1,m)、(n,1)、(n,m)（即矩阵的角）被阻挡。Vova可以从一个空单元格移动到另一个与之共享边的空单元格。Vova可以从矩阵的任何空边界单元格逃脱，这些单元格称为出口。根据Vova可以用来逃脱矩阵的出口数量，Vova定义了矩阵的类型： - 第1类：没有出口可以逃脱的矩阵。 - 第2类：恰好有一个出口可以逃脱的矩阵。 - 第3类：有两个或更多出口可以逃脱的矩阵。 在Vova开始移动之前，Misha可以创建更多障碍物来阻挡更多单元格，但他不能改变矩阵的类型。Misha最多可以阻挡多少个单元格，同时保持矩阵类型不变？Misha不能阻挡Vova当前所在的单元格。 输入输出数据格式： 每个测试用例包含多个测试案例。第一行包含测试案例的数量t(1≤t≤10,000)。接下来是每个测试案例的描述。 每个测试案例的第一行包含两个整数n和m(3≤n,m≤1000)——矩阵的维度。 接下来的n行包含矩阵的描述：第i行(1≤i≤n)包含一个长度为m的字符串，由字符'.'、'#'和'V'组成。第i行的第j个字符描述单元格(i,j)。点'.'表示空单元格，井号'#'表示被阻挡的单元格，字母'V'表示Vova最初所在的空单元格。 保证矩阵的角被阻挡（矩阵描述的第一行和最后一行的第一个和最后一个字符是'#'）。保证字母'V'在矩阵描述中恰好出现一次。 保证所有测试案例的n*m之和不超过1,000,000。 对于每个测试案例，输出一个整数——Misha可以阻挡的最大单元格数。