// #pragma comment(linker, "/stack:200000000")
// #pragma GCC optimize("Ofast,no-stack-protector")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
// #pragma GCC optimize("unroll-loops")

#include <stdio.h>
#include <bits/stdc++.h>

#ifdef PERVEEVM_LOCAL
    #define debug(x...) std::cerr << "[DEBUG]\t" << __LINE__ << ":\t" << (#x) << " = "; print_debug(x)
#else
    #define debug(x...) 238
#endif

#define fastIO std::ios_base::sync_with_stdio(false); std::cin.tie(0); std::cout.tie(nullptr)
#define NAME "File"

using ll = long long;
using ld = long double;

#ifdef PERVEEVM_LOCAL
    std::mt19937 rnd(238);
#else
    std::mt19937 rnd(std::chrono::high_resolution_clock::now().time_since_epoch().count());
#endif

template<typename T1, typename T2>
std::ostream& operator<<(std::ostream& out, const std::pair<T1, T2>& p) {
    out << "(" << p.first << ", " << p.second << ")";
    return out;
}

template<size_t index, typename T>
std::ostream& print_tuple(std::ostream& out, const T& t) {
    if constexpr (index == std::tuple_size<T>::value) {
        out << ")";
        return out;
    } else {
        if (index > 0) {
            out << ", ";
        } else {
            out << "(";
        }
        out << std::get<index>(t);
        return print_tuple<index + 1, T>(out, t);
    }
}

template<typename ...T>
std::ostream& operator<<(std::ostream& out, const std::tuple<T...>& t) {
    return print_tuple<0, std::tuple<T...>>(out, t);
}

template<typename Container, typename = decltype(std::begin(std::declval<Container>()))>
typename std::enable_if<!std::is_same<Container, std::string>::value, std::ostream&>::type
operator<<(std::ostream& out, const Container& container) {
    out << "{";
    for (auto it = container.begin(); it != container.end(); ++it) {
        if (it != container.begin()) {
            out << ", ";
        }
        out << *it;
    }
    out << "}";
    return out;
}

void print_debug() {
    std::cerr << std::endl;
}

template<typename T, typename... V>
void print_debug(const T& value, const V&... others) {
    std::cerr << value;
    if (sizeof...(others) != 0) {
        std::cerr << ", ";
        print_debug(others...);
    } else {
        std::cerr << std::endl;
    }
}

template<typename T>
bool smin(T& a, const T& b) {
    if (b < a) {
        a = b;
        return true;
    }
    return false;
}

template<typename T>
bool smax(T& a, const T& b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

const double PI = atan2(0.0, -1.0);
const int INF = 0x3f3f3f3f;
const ll LINF = (ll)2e18;
const int N = 1100;

const int dx[4] = {-1, 0, 0, 1};
const int dy[4] = {0, -1, 1, 0};

// char a[N][N], b[N][N];
std::vector<std::string> a, b;
int vertices = 0;
int vertexId[N][N];
std::pair<int, int> segmentForVertex[N * N];
std::vector<std::pair<int, int>> g[N * N];
int edgeId = 0;
int up[N * N];
int d[2 * N * N];
std::vector<int> st;
int cc = 0;
std::vector<int> comp;
std::vector<int> points;
std::vector<std::vector<int>> tree;
int par[2 * N * N];
int rowByVertex[N * N];

void init(int n, int m) {
    vertices = 0;
    // memset(vertexId, -1, sizeof(vertexId));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            vertexId[i][j] = -1;
        }
    }
    for (int i = 0; i < n * m; ++i) {
        g[i].clear();
        segmentForVertex[i] = std::make_pair(INF, -INF);
    }
    edgeId = 0;
    // memset(up, INF, sizeof(up));
    // memset(d, -1, sizeof(d));
    for (int i = 0; i < n * m; ++i) {
        up[i] = INF;
    }
    for (int i = 0; i < 2 * n * m; ++i) {
        d[i] = -1;
    }
    st.clear();
    cc = 0;
    comp.clear();
    points.clear();
    tree.clear();
    // memset(par, 0, sizeof(par));
    for (int i = 0; i < 2 * n * m; ++i) {
        par[i] = 0;
    }
}

void dfs(int v, int p = -1) {
    int nch = 0;
    bool isPoint = false;

    for (auto[to, id] : g[v]) {
        if (to == p) {
            continue;
        }
        if (d[to] >= 0) {
            smin(up[v], d[to]);
            if (d[to] < d[v]) {
                st.push_back(id);
            }
            continue;
        }

        d[to] = d[v] + 1;
        st.push_back(id);
        dfs(to, v);
        smin(up[v], up[to]);

        if (up[to] >= d[v]) {
            while (true) {
                int curId = st.back();
                st.pop_back();
                comp[curId] = cc;
                if (curId == id) {
                    break;
                }
            }
            ++cc;
            isPoint = true;
        }
        ++nch;
    }

    if (p < 0) {
        isPoint = nch > 1;
    }
    if (isPoint) {
        points.push_back(v);
    }
}

void dfsTree(int v, int p, int depth = 0) {
    par[v] = p;
    d[v] = depth;
    for (auto to : tree[v]) {
        if (to != p) {
            dfsTree(to, v, depth + 1);
        }
    }
}

std::pair<int, int> getEdgeSegment(int from, int to) {
    int l = std::max(segmentForVertex[from].first, segmentForVertex[to].first);
    int r = std::min(segmentForVertex[from].second, segmentForVertex[to].second);
    if (l > r) {
        return std::make_pair(INF, -INF);
    } else {
        return std::make_pair(l, r);
    }
}

int solvePoint(int pointId, int c1, int c2) {
    int v = points[pointId];

    int l1 = INF, r1 = -INF;
    int l2 = INF, r2 = -INF;
    std::map<int, std::pair<int, int>> otherCompSegments;
    std::vector<std::pair<int, int>> allSegments;
    for (auto[to, id] : g[v]) {
        if (comp[id] == c1) {
            auto[curL, curR] = getEdgeSegment(v, to);
            smin(l1, curL);
            smax(r1, curR);
        } else if (comp[id] == c2) {
            auto[curL, curR] = getEdgeSegment(v, to);
            smin(l2, curL);
            smax(r2, curR);
        } else {
            auto[curL, curR] = getEdgeSegment(v, to);
            if (otherCompSegments.find(comp[id]) == otherCompSegments.end()) {
                otherCompSegments[comp[id]] = std::make_pair(curL, curR);
            } else {
                smin(otherCompSegments[comp[id]].first, curL);
                smax(otherCompSegments[comp[id]].second, curR);
            }
        }
    }
    if (l1 > r1 || l2 > r2) {
        return 1;
    }

    int ans = segmentForVertex[v].second - segmentForVertex[v].first + 1;
    // debug(l1, r1, l2, r2);
    smin(ans, r1 - l1 + 1);
    smin(ans, r2 - l2 + 1);

    int intersectionL = std::max(l1, l2);
    int intersectionR = std::min(r1, r2);
    for (auto[id, seg] : otherCompSegments) {
        allSegments.push_back(seg);
    }
    std::sort(allSegments.begin(), allSegments.end());
    int ptr = -1;
    int minR = intersectionR;
    for (int l = segmentForVertex[v].first; l <= intersectionL; ++l) {
        while (ptr + 1 < (int)allSegments.size() && l > allSegments[ptr + 1].first) {
            ++ptr;
            smax(minR, allSegments[ptr].second);
        }

        // assert(l <= minR);
        // if (std::max(1, minR - l + 1) == 1) {
        //     debug(l1, r1, l2, r2);
        //     debug(allSegments);
        //     debug(intersectionL, intersectionR, l, minR, otherCompSegments, c1, c2, segmentForVertex[v], std::max(1, minR - l + 1));
        //     debug(rowByVertex[v]);
        // }
        smin(ans, std::max(1, minR - l + 1));   // WTF???
    }   

    return ans;
}

int solve(int n, int m) {
    init(n, m);

    int s = -1, t = -1;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (a[i][j] == 's' || a[i][j] == 'f') {
                vertexId[i][j] = vertices;
                rowByVertex[vertices] = i;
                smin(segmentForVertex[vertices].first, j);
                smax(segmentForVertex[vertices].second, j);
                if (a[i][j] == 's') {
                    s = vertices;
                } else {
                    t = vertices;
                }
                ++vertices;
                continue;
            }
            if (a[i][j] != '.') {
                continue;
            }

            if (j - 1 >= 0 && a[i][j - 1] == '.') {
                vertexId[i][j] = vertexId[i][j - 1];
            } else {
                vertexId[i][j] = vertices;
                rowByVertex[vertices] = i;
                ++vertices;
            }

            smin(segmentForVertex[vertexId[i][j]].first, j);
            smax(segmentForVertex[vertexId[i][j]].second, j);
        }
    }

    std::map<std::pair<int, int>, int> edgeSetik;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (vertexId[i][j] == -1) {
                continue;
            }

            int from = vertexId[i][j];
            for (int it = 0; it < 4; ++it) {
                int newI = i + dx[it];
                int newJ = j + dy[it];
                if (newI < 0 || newJ < 0 || newI >= n || newJ >= m) {
                    continue;
                }

                int to = vertexId[newI][newJ];
                if (to == -1 || to == from) {
                    continue;
                }

                if (edgeSetik.find(std::make_pair(from, to)) == edgeSetik.end()) {
                    g[from].emplace_back(to, edgeId);
                    edgeSetik[std::make_pair(from, to)] = edgeId;
                    edgeSetik[std::make_pair(to, from)] = edgeId;
                    ++edgeId;
                } else {
                    int id = edgeSetik[std::make_pair(from, to)];
                    g[from].emplace_back(to, id);
                }
            }
        }
    }

    comp.resize(edgeId);
    d[s] = 0;
    dfs(s);

    int L = (int)points.size();
    int R = cc;
    tree.resize(L + R);
    std::set<std::pair<int, int>> edges;
    for (int i = 0; i < (int)points.size(); ++i) {
        int v = points[i];
        for (auto[to, id] : g[v]) {
            int l = i;
            int r = comp[id];
            if (edges.emplace(l, r).second) {
                tree[l].push_back(r + L);
                tree[r + L].push_back(l);
            }
        }
    }

    int treeS = -1, treeT = -1;
    for (int i = 0; i < (int)points.size(); ++i) {
        int v = points[i];
        if (v == s) {
            treeS = i;
        }
        if (v == t) {
            treeT = i;
        }
    }

    if (treeS == -1) {
        int cmpId = -1;
        for (auto[to, id] : g[s]) {
            if (cmpId == -1) {
                cmpId = comp[id];
            }
            assert(cmpId == comp[id]);
        }
        treeS = cmpId + L;
    }
    if (treeT == -1) {
        int cmpId = -1;
        for (auto[to, id] : g[t]) {
            if (cmpId == -1) {
                cmpId = comp[id];
            }
            assert(cmpId == comp[id]);
        }
        treeT = cmpId + L;
    }

    assert(treeS != -1);
    assert(treeT != -1);

    dfsTree(treeS, treeS);

    std::vector<int> path;
    for (int i = treeT; i != treeS; i = par[i]) {
        path.push_back(i);
    }
    path.push_back(treeS);

    int ans = INF;
    for (int i = 1; i < (int)path.size() - 1; ++i) {
        int curV = path[i];
        if (curV < L) {
            smin(ans, solvePoint(curV, path[i - 1] - L, path[i + 1] - L));
        }
    }
    // if (treeS < L) {
    //     smin(ans, solvePoint(treeS, path[1] - L, -1));
    // }
    // if (treeT < L) {
    //     smin(ans, solvePoint(treeT, path[(int)path.size() - 2] - L, -1));
    // }

    return ans;
}

void solve() {
    int n, m;
    std::cin >> n >> m;
    
    a.assign(n, std::string(m, '.'));
    b.assign(m, std::string(n, '.'));

    for (int i = 0; i < n; ++i) {
        std::cin >> a[i];
        for (int j = 0; j < m; ++j) {
            b[j][i] = a[i][j];
        }
    }

    int ans = solve(n, m);
    std::swap(a, b);
    std::swap(n, m);
    smin(ans, solve(n, m));

    if (ans == INF) {
        std::cout << "-1\n";
    } else {
        std::cout << ans << '\n';
    }
}

void run() {
    fastIO;
    
    int t;
    std::cin >> t;
    
    while (t--) {
        solve();
    }
}

int main(void) {
    // freopen(NAME".in", "r", stdin);
    // freopen(NAME".out", "w", stdout);

    #ifdef PERVEEVM_LOCAL
        auto start = std::chrono::high_resolution_clock::now();
    #endif

    run();

    #ifdef PERVEEVM_LOCAL
        auto end = std::chrono::high_resolution_clock::now();
        std::cerr << "Execution time: "
                  << std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count()
                  << " ms" << std::endl;
    #endif

    return 0;
}
