Barrett 在他家地下发现了一个古老的迷宫。迷宫呈 $n \times m$ 的网格状，其中一些单元格是空的，另一些是阻挡的。如果两个空单元格共享一条边，则可以从一个走到另一个。其中两个空单元格分别是入口和出口，并且可以通过走空单元格从入口到达出口。

Barrett 想要通过在迷宫内建造一堵墙来隔离他的房子，通过阻挡一些单元格使得出口无法从入口到达。这堵墙必须是直的，且方向为垂直或水平。具体来说，长度为 $k$ 的墙将阻挡连续的一行或一列中恰好 $k$ 个单元格。墙不能包含入口、出口或任何已经阻挡的单元格。

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

输入格式

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$ ($1 \le t \le 10^5$)。

接下来是测试用例的描述。

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

接下来的 $n$ 行，每行包含 $m$ 个字符，描述迷宫的第 $i$ 行，其中： ‘.’ 表示一个空单元格； ‘#’ 表示一个阻挡的单元格； ‘s’ 表示一个入口单元格； ‘f’ 表示一个出口单元格。

迷宫恰好包含一个入口单元格和一个出口单元格，并且可以通过走空单元格从入口到达出口。

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

输出格式

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

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

样例

输入 1

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

输出 1

1
2
-1