题目描述

Barrett 在自家房子下面发现了一座古老迷宫。迷宫是一个 $n\times m$ 的网格，其中一些格子为空，另一些格子被障碍物阻塞。两个空格子若共用一条边，就可以在它们之间移动。

迷宫中有两个特殊的空格子，分别是入口和出口。初始时，可以从入口经由空格子走到出口。

Barrett 想在迷宫中修建一堵墙，阻塞若干格子，使得出口不再能从入口到达。墙必须是一条水平或竖直的直线段。

具体来说，一堵长度为 $k$ 的墙会阻塞同一行或同一列中连续的恰好 $k$ 个格子。墙不能覆盖入口、出口或任何原本已经被阻塞的格子。

请你求出墙的最小可能长度。

输入格式

每个输入包含多组测试数据。

第一行包含一个整数 $t$，表示测试数据组数。

对于每组测试数据：

• 第一行包含两个整数 $n,m$，分别表示迷宫的高度和宽度；
• 接下来 $n$ 行，每行包含 $m$ 个字符，描述迷宫的第 $i$ 行：
  • . 表示空格子；
  • # 表示被阻塞的格子；
  • s 表示入口；
  • f 表示出口。

迷宫中恰好有一个入口和一个出口，并且初始时二者互相可达。

数据范围

所有测试数据的 $n\cdot m$ 之和不超过 $10^6$。

输出格式

对于每组测试数据，输出一个整数，表示使入口与出口不再连通所需墙的最小长度。

若无法修建满足要求的墙，输出 $-1$。

样例

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

1
2
-1