Description

Barrett has discovered an ancient maze under his house. It has the shape of an $n \times m$ grid, where some cells are empty, while others are blocked. It is possible to walk from one empty cell to another if they share a side. Two of the empty cells are an entrance and an exit, and it is possible to reach one from the other by walking through empty cells.

Barrett wants to isolate his house by building a wall inside the maze, blocking some cells to make the exit unreachable from the entrance. The wall should be straight and oriented either vertically or horizontally. Specifically, a wall of length $k$ will block a consecutive row or column of exactly $k$ cells. The wall may not contain the entrance, the exit, or any already blocked cells.

Help Barrett determine the minimum possible length of the wall.

Input Format

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^5$). The description of the test cases follows.

The first line of each test case contains two integers $n$ and $m$, denoting the height and the width of the~maze ($2 \le n, m \le 1000$).

The $i$-th of the following $n$ lines contains $m$ characters and describes the $i$-th row of the maze, where:

• $\texttt{.}$ denotes an empty cell;
• $\texttt{\#}$ denotes a blocked cell;
• $\texttt{s}$ denotes an entrance cell;
• $\texttt{f}$ denotes an exit cell.

The maze contains exactly one entrance cell and exactly one exit cell, and it is possible to reach one from the other by walking through empty cells.

It is guaranteed that the sum of $n \cdot m$ over all test cases does not exceed $10^6$.

Output Format

For each test case, print the minimum length of the wall required to make the exit unreachable from the entrance.

If it is impossible to build such a wall, print $-1$ instead.

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

1
2
-1