题目描述

Barrett 在他的房子下方发现了一个古老的迷宫。该迷宫呈 $n \times m$ 网格状，其中部分格子为空地，其他则为障碍物。若两个空格子共享一条边，则可以从一个格子走到另一个。迷宫中有一个入口格子和一个出口格子，且可以通过空格子从入口走到出口。

Barrett 希望通过在迷宫中建造一堵墙来隔离他的房子，通过阻挡部分格子使得出口无法从入口到达。这堵墙必须是笔直的，且方向只能是垂直或水平。具体而言，长度为 $k$ 的墙将阻挡恰好 $k$ 个连续的行或列格子。墙不能包含入口、出口或任何已有障碍物的格子。

请帮助 Barrett 确定这堵墙的最小可能长度。

输入格式

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^5$）。接下来是各测试用例的描述。

每个测试用例的第一行包含两个整数 $n$ 和 $m$，分别表示迷宫的高度和宽度（$2 \le n, m \le 1000$）。

接下来的 $n$ 行中，第 $i$ 行包含 $m$ 个字符，描述迷宫的第 $i$ 行，其中：

• $\texttt{.}$ 表示空格子；
• $\texttt{\#}$ 表示障碍物格子；
• $\texttt{s}$ 表示入口格子；
• $\texttt{f}$ 表示出口格子。

迷宫中恰好有一个入口格子和一个出口格子，且可以通过空格子从入口走到出口。

保证所有测试用例的 $n \cdot m$ 之和不超过 $10^6$。

输出格式

对于每个测试用例，输出使得出口无法从入口到达所需建造的墙的最小长度。

如果无法建造这样的墙，则输出 $-1$。

3
3 3
s.#
...
#.f
6 7
..#.#..
s..#..#
....#f.
#..#...
#......
#.....#
2 2
s.
.f

1
2
-1