F. Вова и побег из матрицы
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вова находится в матрице $$$n \times m$$$. Строки этой матрицы пронумерованы числами от $$$1$$$ до $$$n$$$ сверху вниз, а столбцы пронумерованы числами от $$$1$$$ до $$$m$$$ слева направо. Клетка $$$(i, j)$$$ — это клетка на пересечении строки $$$i$$$ и столбца $$$j$$$ для $$$1 \leq i \leq n$$$ и $$$1 \leq j \leq m$$$.

Часть клеток матрицы заблокирована препятствиями (все остальные клетки свободны). Вова находится в одной из свободных клеток. Гарантируется, что клетки $$$(1, 1)$$$, $$$(1, m)$$$, $$$(n, 1)$$$, $$$(n, m)$$$ (то есть углы матрицы) заблокированы.

Вова может перейти из одной свободной клетки в другую свободную клетку, если у них есть общая сторона. Вова может выйти из матрицы из любой свободной клетки на границе матрицы, такие клетки называются выходами.

Тип матрицы зависит от количества выходов, которые Вова может использовать, чтобы выйти из матрицы. Существуют матрицы трёх типов:

  • $$$1$$$-го типа: матрицы без выходов, которые Вова может использовать.
  • $$$2$$$-го типа: матрицы ровно с одним выходом, который Вова может использовать, чтобы покинуть матрицу.
  • $$$3$$$-го типа: матрицы с несколькими (двумя или более) выходами, которые Вова может использовать, чтобы покинуть матрицу.

До того как Вова начнёт перемещаться, Миша может создать больше препятствий и заблокировать часть свободных клеток. При этом Миша не может менять тип матрицы. Какое максимальное количество клеток может заблокировать Миша, не изменяя тип матрицы? Миша не может заблокировать клетку, в которой сейчас находится Вова.

Входные данные

В первой строке задано одно целое число $$$t$$$ ($$$1 \leq t \leq 10\,000$$$) — количество наборов входных данных. Далее следуют описания этих наборов.

В первой строке дано два целых числа $$$n$$$ и $$$m$$$ ($$$3 \leq n,m \leq 1000$$$) — размеры матрицы.

В следующих $$$n$$$ строках дано описание матрицы: в $$$i$$$-й ($$$1 \le i \le n$$$) из них дана строка длины $$$m$$$, состоящая из символов «.», «#» и «V». $$$j$$$-й символ $$$i$$$-й строки описывает клетку $$$(i, j)$$$ матрицы. Точкой «.» обозначена свободная клетка, решёткой «#» обозначена заблокированная клетка, буквой «V» обозначена свободная клетка, в которой находится Вова.

Гарантируется, что углы матрицы заблокированы (первый и последний символы первой и последней строк описания матрицы равны «#»). Гарантируется, что символ «V» встречается в матрице ровно один раз.

Гарантируется, что сумма $$$n \cdot m$$$ по всем наборам входных данных не превосходит $$$1\,000\,000$$$.

Выходные данные

Для каждого набора входных данных выведите одно число: максимальное количество клеток, которые может заблокировать Миша.

Пример
Входные данные
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##
##.##
#...#
Выходные данные
9
0
0
3
4
10
12
5
Примечание

В первом наборе входных данных дана матрица $$$3$$$-го типа. Миша может заблокировать все клетки, кроме клеток $$$(1, 3)$$$, $$$(2, 3)$$$, $$$(2, 4)$$$. Существует $$$9$$$ таких клеток и их блокировка не меняет тип матрицы.

Во втором наборе входных данных дана матрица $$$3$$$-го типа. Блокировка любой клетки меняет тип матрицы на $$$2$$$-й: один из двух выходов становится недостижимым для Вовы. Поэтому, ответ $$$0$$$.

В третьем наборе входных данных дана матрица $$$1$$$-го типа. В ней нет свободных клеток (кроме клетки Вовы), поэтому Миша не может заблокировать ни одну клетку.

В четвёртом наборе входных данных дана матрица $$$2$$$-го типа. Миша может заблокировать $$$3$$$ клетки $$$(5, 2)$$$, $$$(6, 3)$$$, $$$(6, 4)$$$, не изменяя тип матрицы.

В пятом наборе входных данных дана матрица $$$3$$$-го типа. Миша может заблокировать $$$4$$$ клетки $$$(2, 2)$$$, $$$(3, 2)$$$, $$$(4, 2)$$$, $$$(5, 2)$$$ либо $$$4$$$ клетки $$$(2, 4)$$$, $$$(3, 4)$$$, $$$(4, 4)$$$, $$$(5, 4)$$$, не изменяя тип матрицы.