#include <bits/stdc++.h>

using namespace std;

template <class T>
bool smin(T & x, T y) {
    if (x > y) {
        x = y;
        return true;
    }
    return false;
}

template <class T>
bool smax(T & x, T y) {
    if (x < y) {
        x = y;
        return true;
    }
    return false;
}

struct dsu {
    int n;
    vector<int> p;
    vector<int> sz;
    vector<bool> s;
    vector<bool> f;

    dsu() {}
    dsu(int n) {
        this->n = n;
        p.assign(n, 0);
        sz.assign(n, 1);
        s.assign(n, false);
        f.assign(n, false);
        for (int i = 0; i < n; ++i) {
            p[i] = i;
        }
    }

    int get(int v) {
        if (p[v] == v) {
            return v;
        }
        return p[v] = get(p[v]);
    }

    bool unite(int a, int b) {
        a = get(a);
        b = get(b);
        if (a == b) {
            return false;
        }
        if (sz[a] < sz[b]) {
            swap(a, b);
        }
        p[b] = a;
        sz[a] += sz[b];
        if (s[b]) {
            s[a] = true;
        }
        if (f[b]) {
            f[a] = true;
        }
        return true;
    }

    void set_s(int v) {
        s[get(v)] = true;
    }

    void set_f(int v) {
        f[get(v)] = true;
    }

    bool get_s(int v) {
        return s[get(v)];
    }

    bool get_f(int v) {
        return f[get(v)];
    }
};

int N = 1010;

vector<vector<bool>> transpose(int n, int m, vector<vector<bool>> & field) {
    vector<vector<bool>> ans(m, vector<bool>(n));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            ans[j][i] = field[i][j];
        }
    }
    return ans;
}

int calc_hor(int n, int m, vector<vector<bool>> & field, pair<int, int> & s, pair<int, int> & f) {
    vector<dsu> pref(n + 2);
    vector<dsu> suf(n + 2);
    for (int i = 0; i < n + 2; ++i) {
        pref[i] = dsu(m);
        suf[i] = dsu(m);
    }
    for (int i = 0; i < n; ++i) {
        vector<int> p(m);
        for (int j = 0; j < m; ++j) {
            p[j] = pref[i].get(j);
        }
        vector<int> first(m, -1);
        for (int j = 0; j < m; ++j) {
            if (field[i][j] && first[p[j]] == -1) {
                first[p[j]] = j;
            }
        }
        for (int j = 0; j < m; ++j) {
            if (s == pair{i, j} || (field[i][j] && pref[i].get_s(j))) {
                pref[i + 1].set_s(j);
            }
            if (f == pair{i, j} || (field[i][j] && pref[i].get_f(j))) {
                pref[i + 1].set_f(j);
            }
        }
        for (int j = 0; j < m; ++j) {
            if (field[i][j]) {
                pref[i + 1].unite(first[p[j]], j);
            }
        }
        for (int j = 0; j < m - 1; ++j) {
            if (field[i][j] && field[i][j + 1]) {
                pref[i + 1].unite(j, j + 1);
            }
        }
    }
    for (int i = n - 1; i >= 0; --i) {
        vector<int> p(m);
        for (int j = 0; j < m; ++j) {
            p[j] = suf[i + 2].get(j);
        }
        vector<int> first(m, -1);
        for (int j = 0; j < m; ++j) {
            if (field[i][j] && first[p[j]] == -1) {
                first[p[j]] = j;
            }
        }
        for (int j = 0; j < m; ++j) {
            if (s == pair{i, j} || (field[i][j] && suf[i + 2].get_s(j))) {
                suf[i + 1].set_s(j);
            }
            if (f == pair{i, j} || (field[i][j] && suf[i + 2].get_f(j))) {
                suf[i + 1].set_f(j);
            }
        }
        for (int j = 0; j < m; ++j) {
            if (field[i][j]) {
                suf[i + 1].unite(j, first[p[j]]);
            }
        }
        for (int j = 0; j < m - 1; ++j) {
            if (field[i][j] && field[i][j + 1]) {
                suf[i + 1].unite(j, j + 1);
            }
        }
    }
    int ans = N;
    for (int i = 0; i < n; ++i) {
        dsu dsu0(3 * m);
        for (int j = 0; j < m; ++j) {
            dsu0.unite(j, pref[i].get(j));
            if (pref[i].get_s(j)) {
                dsu0.set_s(j);
            }
            if (pref[i].get_f(j)) {
                dsu0.set_f(j);
            }
            dsu0.unite(m + j, m + suf[i + 2].get(j));
            if (suf[i + 2].get_s(j)) {
                dsu0.set_s(m + j);
            }
            if (suf[i + 2].get_f(j)) {
                dsu0.set_f(m + j);
            }
            if (s == pair{i, j}) {
                dsu0.set_s(2 * m + j);
            } else if (f == pair{i, j}) {
                dsu0.set_f(2 * m + j);
            }
        }
        int spos = -1;
        int fpos = -1;
        for (int j = 0; j < 3 * m; ++j) {
            if (dsu0.get_s(j)) {
                spos = dsu0.get(j);
            }
            if (dsu0.get_f(j)) {
                fpos = dsu0.get(j);
            }
        }
        if (fpos == spos) {
            continue;
        }
        if (spos < 0 || fpos < 0) {
            continue;
        }
        vector<int> nxt(m + 1);
        nxt[m] = m;
        for (int j = m - 1; j >= 0; --j) {
            if (!field[i][j] || s == pair{i, j} || f == pair{i, j}) {
                nxt[j] = j;
            } else {
                nxt[j] = nxt[j + 1];
            }
        }
        for (int l = 0; l < m; ++l) {
            if (nxt[l] == l) {
                if (s == pair{i, l} || f == pair{i, l}) {
                    dsu0.unite(l, 2 * m + l);
                    dsu0.unite(m + l, 2 * m + l);
                    if (l > 0 && field[i][l - 1]) {
                        dsu0.unite(2 * m + l - 1, 2 * m + l);
                    }
                    if (dsu0.get(fpos) == dsu0.get(spos)) {
                        break;
                    }
                }
                continue;
            }
            dsu dsu1 = dsu0;
            for (int k = m - 1; k >= l; --k) {
                if (!field[i][k]) {
                    continue;
                }
                dsu1.unite(k, 2 * m + k);
                dsu1.unite(m + k, 2 * m + k);
                if (k + 1 < m && field[i][k + 1]) {
                    dsu1.unite(2 * m + k, 2 * m + k + 1);
                }
                if (k == l && k > 0 && field[i][k - 1]) {
                    dsu1.unite(2 * m + k, 2 * m + k - 1);
                }
                if (dsu1.get(spos) == dsu1.get(fpos)) {
                    if (k < nxt[l]) {
                        smin(ans, k - l + 1);
                    }
                    break;
                }
            }
            dsu0.unite(l, 2 * m + l);
            dsu0.unite(m + l, 2 * m + l);
            if (l > 0 && field[i][l - 1]) {
                dsu0.unite(2 * m + l - 1, 2 * m + l);
            }
            if (dsu0.get(fpos) == dsu0.get(spos)) {
                break;
            }
        }
    }
    return ans;
}

void solve() {
    int n, m;
    cin >> n >> m;
    vector<vector<bool>> field(n, vector<bool>(m, true));
    pair<int, int> s, f;
    for (int i = 0; i < n; ++i) {
        string str;
        cin >> str;
        for (int j = 0; j < m; ++j) {
            if (str[j] == '#') {
                field[i][j] = false;
            } else if (str[j] == 's') {
                s = {i, j};
            } else if (str[j] == 'f') {
                f = {i, j};
            }
        }
    }
    int val1 = calc_hor(n, m, field, s, f);
    swap(s.first, s.second);
    swap(f.first, f.second);
    field = transpose(n, m, field);
    swap(n, m);
    int val2 = calc_hor(n, m, field, s, f);
    int val = min(val1, val2);
    if (val == N) {
        cout << "-1\n";
    } else {
        cout << val << "\n";
    }
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}
