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:

\begin{itemize}
\item \vspace{-1.2em} `\texttt{.}' denotes an empty cell;
\item \vspace{-0.7em} `\texttt{\#}' denotes a blocked cell;
\item \vspace{-0.7em} `\texttt{s}' denotes an entrance cell;
\item \vspace{-0.7em} `\texttt{f}' denotes an exit cell.\vspace{-1.2em}
\end{itemize}

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$.