// #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 used[N][N];
int usedVersion = 0;

void dfs(int x, int y, int n, int m) {
    used[x][y] = usedVersion;

    for (int i = 0; i < 4; ++i) {
        int newX = x + dx[i];
        int newY = y + dy[i];
        if (newX < 0 || newY < 0 || newX >= n || newY >= m) {
            continue;
        }
        if (a[newX][newY] == '#') {
            continue;
        }
        if (used[newX][newY] == usedVersion) {
            continue;
        }
        dfs(newX, newY, n, m);
    }
}

bool check(int n, int m, int k) {
    int sx = -1, sy = -1;
    int tx = -1, ty = -1;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (a[i][j] == 's') {
                sx = i;
                sy = j;
            }
            if (a[i][j] == 'f') {
                tx = i;
                ty = j;
            }
        }
    }

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (a[i][j] != '.') {
                continue;
            }

            int cnt = 0;
            for (int it = 0; it < k && j + it < m; ++it) {
                if (a[i][j + it] != '.') {
                    break;
                }
                ++cnt;
                a[i][j + it] = '#';
            }
            assert(cnt <= k);
            ++usedVersion;
            dfs(sx, sy, n, m);
            for (int it = 0; it < cnt; ++it) {
                a[i][j + it] = '.';
            }

            if (used[tx][ty] != usedVersion) {
                return true;
            }
        }
    }

    return false;
}

int solve(int n, int m) {
    int l = 0, r = m + 1;
    while (r - l > 1) {
        int mid = (l + r) / 2;

        if (check(n, m, mid)) {
            r = mid;
        } else {
            l = mid;
        }
    }

    if (r == m + 1) {
        return INF;
    } else {
        return r;
    }
}

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;
}
