벽 쌓기 2

Barrett는 집 아래에서 오래된 미로를 발견했다. 미로는 $n \times m$ 격자 모양이며, 일부 칸은 비어 있고 나머지 칸은 막혀 있다. 변을 공유하는 두 빈 칸은 서로 오갈 수 있다. 빈 칸 중 하나는 입구이고 다른 하나는 출구이며, 빈 칸만 거쳐 한쪽에서 다른 쪽으로 갈 수 있다.

Barrett는 미로 안에 벽을 세워 입구에서 출구로 갈 수 없게 만들고, 그렇게 집을 고립시키려 한다. 벽은 세로 또는 가로로 곧게 세워야 한다. 길이가 $k$인 벽은 한 행 또는 한 열의 연속된 $k$개 칸을 막는다. 벽은 입구, 출구, 이미 막힌 칸을 포함할 수 없다.

세울 수 있는 벽의 최소 길이를 구하라.

여러 테스트 케이스가 주어진다. 첫 줄에 테스트 케이스의 개수 $t$($1 \le t \le 10^5$)가 주어진다.

각 테스트 케이스의 첫 줄에는 미로의 높이와 너비를 뜻하는 정수 $n$과 $m$($2 \le n, m \le 1000$)이 주어진다. 이어서 $n$개의 줄에 미로의 각 행이 $m$개의 문자로 주어진다.

• .는 빈 칸이다.
• #는 막힌 칸이다.
• s는 입구다.
• f는 출구다.

각 미로에는 입구와 출구가 정확히 하나씩 있으며, 빈 칸을 거쳐 서로 갈 수 있다.

모든 테스트 케이스의 $n \cdot m$ 합은 $10^6$을 넘지 않는다.

각 테스트 케이스마다 출구에 도달할 수 없게 만드는 벽의 최소 길이를 한 줄에 출력한다. 그런 벽을 세울 수 없으면 $-1$을 출력한다.