/**
 *    author:  tourist
 *    created: 11.11.2024 08:20:52
**/
#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int tt;
  cin >> tt;
  while (tt--) {
    int h, w;
    cin >> h >> w;
    vector<string> s(h);
    for (int i = 0; i < h; i++) {
      cin >> s[i];
    }
    const int inf = int(1e9);
    int ans = inf;
    for (int rot = 0; rot < 2; rot++) {
      // Identifying the vertices
      vector<vector<int>> idx(h, vector<int>(w, -1));
      vector<array<int, 3>> vers;
      int cnt = 0;
      int start = -1;
      int finish = -1;
      for (int i = 0; i < h; i++) {
        int beg = 0;
        while (beg < w) {
          if (s[i][beg] == '#') {
            beg += 1;
            continue;
          }
          if (s[i][beg] == 's') {
            start = cnt;
            idx[i][beg] = cnt;
            vers.push_back({i, beg, beg});
            cnt += 1;
            beg += 1;
            continue;
          }
          if (s[i][beg] == 'f') {
            finish = cnt;
            idx[i][beg] = cnt;
            vers.push_back({i, beg, beg});
            cnt += 1;
            beg += 1;
            continue;
          }
          assert(s[i][beg] == '.');
          int end = beg;
          while (end + 1 < w && s[i][end + 1] == '.') {
            end += 1;
          }
          for (int j = beg; j <= end; j++) {
            idx[i][j] = cnt;
          }
          vers.push_back({i, beg, end});
          cnt += 1;
          beg = end + 1;
        }
      }

      // Building the edges
      vector<vector<int>> g(cnt);
      auto Add = [&](int a, int b) {
        if (a != -1 && b != -1 && a != b) {
          g[a].push_back(b);
          g[b].push_back(a);
        }
      };
      for (int i = 0; i < h; i++) {
        for (int j = 0; j < w - 1; j++) {
          Add(idx[i][j], idx[i][j + 1]);
        }
      }
      for (int i = 0; i < h - 1; i++) {
        for (int j = 0; j < w; j++) {
          Add(idx[i][j], idx[i + 1][j]);
        }
      }

      // Traversing the graph
      vector<int> tin(cnt, -1);
      vector<int> tout(cnt, -1);
      vector<int> up(cnt, inf);
      vector<int> pv(cnt, -1);
      vector<vector<int>> children(cnt);
      int T = 0;
      auto Dfs = [&](auto&& self, int v) -> void {
        tin[v] = T++;
        for (int u : g[v]) {
          if (pv[u] == -1) {
            children[v].push_back(u);
            pv[u] = v;
            self(self, u);
            up[v] = min(up[v], up[u]);
          } else {
            up[v] = min(up[v], tin[u]);
          }
        }
        tout[v] = T;
      };
      pv[start] = -2;
      Dfs(Dfs, start);

      auto IsAnc = [&](int u, int v) {
        return tin[u] <= tin[v] && tout[v] <= tout[u];
      };

      // Calculating the answer
      int v = finish;
      while (pv[v] != start) {
        int u = pv[v];
        if (up[v] >= tin[u]) {
          vector<int> aux;
          auto Check = [&](int i, int j) {
            if (i >= 0 && j >= 0 && i < h && j < w) {
              if (s[i][j] != '#') {
                int to = idx[i][j];
                if (to != u) {
                  if (IsAnc(v, to)) {
                    return 1;
                  }
                  if (!IsAnc(u, to)) {
                    return 2;
                  }
                  int low = 0, high = int(children[u].size());
                  while (low + 1 < high) {
                    int mid = (low + high) >> 1;
                    if (tin[children[u][mid]] <= tin[to]) {
                      low = mid;
                    } else {
                      high = mid;
                    }
                  }
                  int rep = children[u][low];
                  if (up[rep] < tin[u]) {
                    return 2;
                  }
                  aux.push_back(rep);
                }
              }
            }
            return 0;
          };
          auto& [i, j1, j2] = vers[u];
          vector<int> masks;
          vector<vector<int>> others;
          for (int j = j1; j <= j2; j++) {
            aux.clear();
            masks.push_back(Check(i, j - 1) | Check(i, j + 1) | Check(i - 1, j) | Check(i + 1, j));
            others.push_back(aux);
          }
          debug(masks, others);
          int sz = int(masks.size());
          for (int bit = 1; bit <= 2; bit++) {
            int first = -1;
            int last = -1;
            for (int it = 0; it < sz; it++) {
              if (masks[it] & bit) {
                if (first == -1) {
                  first = it;
                }
                last = it;
              }
            }
            assert(first != -1);
            ans = min(ans, last - first + 1);
          }
        }
        v = u;
      }

      swap(h, w);
      vector<string> new_s(h, string(w, ' '));
      for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
          new_s[i][j] = s[j][i];
        }
      }
      swap(s, new_s);
    }
    cout << (ans == inf ? -1 : ans) << '\n';
  }
  return 0;
}
