#include <bits/stdc++.h>
using namespace std;

struct UF {
    int n;
    vector<int> par;
    UF(int _n) : n(_n) {
        for(int i = 0; i < n; i++) par.push_back(i);
    }
    int find(int a){
        if(a != par[a]) par[a] = find(par[a]);
        return par[a];
    }
    bool join(int a, int b){
        a = find(a);
        b = find(b);
        par[a] = b;
        return (a != b);
    }
};

void solve(){
	int N, M;
	cin >> N >> M;
	vector<string> S(N);
	for(int i = 0; i < N; i++){
		cin >> S[i];
	}
	const int INF = 1e8;
	int ans = INF;
	for(int dir = 0; dir < 2; dir++){
		pair<int,int> start {-1, -1}, finish {-1, -1};
		for(int i = 0; i < N; i++){
			for(int j = 0; j < M; j++){
				if(S[i][j] == 's'){
					start = {i, j};
				}
				if(S[i][j] == 'f'){
					finish = {i, j};
				}
			}
		}
		assert(start.first != -1 && finish.first != -1);
		vector<vector<int> > horz_cross(N+1, vector<int>(M, 0));
		vector<vector<int> > vert_cross(N, vector<int>(M+1, 0));
		for(pair<int,int> p : {start, finish}){
			for(int i = p.second; i >= 0; i--){
				vert_cross[p.first][i] ^= 1;
			}
		}
		int V = (N+1) * (M+1);
		vector<vector<int> > horz(N+1, vector<int>(M, 0));
		vector<vector<int> > vert(N, vector<int>(M+1, 0));
		for(int i = 0; i < N; i++){
			vert[i][0] = vert[i][M] = 1;
		}
		for(int i = 0; i < M; i++){
			horz[0][i] = horz[N][i] = 1;
		}
		for(int i = 0; i < N; i++){
			for(int j = 0; j < M; j++){
				if(S[i][j] == '#'){
					horz[i][j] = horz[i+1][j] = 1;
					vert[i][j] = vert[i][j+1] = 1;
				}
			}
		}
		auto convert = [&](int i, int j){
			return i*(M+1) + j;
		};
		UF uf(2*V);
		for(int i = 0; i <= N; i++){
			for(int j = 0; j < M; j++){
				if(horz[i][j]){
					int cross = horz_cross[i][j];
					assert(cross == 0);
					uf.join(convert(i, j), convert(i, j+1) + V * cross);
					uf.join(convert(i, j) + V, convert(i, j+1) + V * (1-cross));
				}
			}
		}
		for(int i = 0; i < N; i++){
			for(int j = 0; j <= M; j++){
				if(vert[i][j]){
					int cross = vert_cross[i][j];
					uf.join(convert(i, j), convert(i+1, j) + V * cross);
					uf.join(convert(i, j) + V, convert(i+1, j) + V * (1-cross));
				}
			}
		}
		for(int i = 0; i < V; i++){
			assert(uf.find(i) != uf.find(i+V));
		}
		vector<vector<int> > ccs(2*V);
		for(int i = 0; i < 2*V; i++){
			ccs[uf.find(i)].push_back(i);
		}

		vector<vector<int> > can_place(N, vector<int>(M, 0));
		for(int i = 0; i < N; i++){
			for(int j = 0; j < M; j++){
				if(S[i][j] == '.') can_place[i][j] = 1;
			}
		}
		vector<vector<int> > place_len(N, vector<int>(M, 0));
		for(int i = 0; i < N; i++){
			for(int j = M-1; j >= 0; j--){
				if(can_place[i][j]){
					place_len[i][j] = 1 + (j + 1 < M ? place_len[i][j+1] : 0);
				}
			}
		}

		vector<vector<set<int> > > points(N+1, vector<set<int>>(2));

		for(int i = 0; i < 2*V; i++){
			if(ccs[i].empty()) continue;
			vector<tuple<int,int,int> > cc;
			for(int v : ccs[i]){
				int side = v / V;
				v %= V;
				int x = v / (M+1);
				int y = v % (M+1);
				cc.push_back({x, y, side});
			}
			for(auto [x, y, side] : cc){
				points[x][side].insert(y);
			}
			for(auto [x, y, side] : cc){
				for(int bx : {x, x-1}){
					for(int by : {y}){
						// left y
						if(bx < 0 || by < 0 || bx >= N || by >= M) continue;
						if(!can_place[bx][by]) continue;
						for(int px : {bx, bx + 1}){
							for(int dest_side : {0, 1}){
								auto r = points[px][dest_side].lower_bound(y+1);
								if(r == points[px][dest_side].end()) continue;
								int right_y = *r - 1;
								if(right_y - by + 1 > place_len[bx][by]) continue;

								// check side
								int net_side = side ^ dest_side;
								if(px != x) net_side ^= vert_cross[min(bx, px)][by];
								// assert(uf.find(convert(x, y) + V * side) == uf.find(convert(px, right_y + 1) + V * dest_side));
								if(net_side == 1){
									ans = min(ans, right_y - by + 1);
									// vector<string> T = S;
									// cerr << "side " << side << '\n';
									// cerr << px << ' ' << y << ' ' << dest_side << '\n';
									// for(int z = by; z <= right_y; z++){
									// 	T[bx][z] = 'x';
									// }
									// for(string s : T) cerr << s << '\n';
									// cerr << '\n';
								}
							}
						}
					}
				}
			}
			for(auto [x, y, side] : cc){
				points[x][side].erase(y);
			}
		}

		{
			vector<string> tS(M);
			for(int i = 0; i < N; i++){
				for(int j = 0; j < M; j++){
					tS[j].push_back(S[i][j]);
				}
			}
			S = tS;
			swap(N, M);
		}
	}
	if(ans == INF) ans = -1;
	cout << ans << '\n';
}

int main(){
	ios_base::sync_with_stdio(false), cin.tie(nullptr);
	int T;
	cin >> T;
	while(T--) solve();
	
}
