Brick in the Wall, Part 2

Barrett has discovered an ancient maze under his house. It is an $n \times m$ grid where some cells are empty and others are blocked. Two empty cells are adjacent if they share a side. One empty cell is the entrance and another is the exit, and you can walk from one to the other through empty cells.

Barrett wants to isolate his house by building a wall inside the maze so that the exit cannot be reached from the entrance. The wall must be straight, either vertical or horizontal. A wall of length $k$ blocks exactly $k$ consecutive cells in one row or one column. The wall may not include the entrance, the exit, or any cell that is already blocked.

Find the minimum possible length of the wall.

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

The first line of each test case contains two integers $n$ and $m$, the height and the width of the maze ($2 \le n, m \le 1000$). The next $n$ lines each contain $m$ characters describing one row of the maze:

• . is an empty cell.
• # is a blocked cell.
• s is the entrance.
• f is the exit.

Each maze contains exactly one entrance and exactly one exit, and you can walk from one to the other through empty cells.

The sum of $n \cdot m$ over all test cases does not exceed $10^6$.

For each test case, print the minimum length of a wall that makes the exit unreachable from the entrance. If no such wall can be built, print $-1$.