#include "testlib.h"

const int MAXN = 1'000;
const int MAXT = 100'000;
const int MAXSUM = 1'000'000;

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

int sumNM = 0;
int n, m;
std::vector<std::string> a;
std::vector<std::vector<bool>> used;

void dfs(int x, int y) {
    used[x][y] = true;

    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 (used[newX][newY] || a[newX][newY] == '#') {
            continue;
        }
        dfs(newX, newY);
    }
}

void readTestCase() {
    n = inf.readInt(2, MAXN, "n");
    inf.readSpace();
    m = inf.readInt(2, MAXN, "m");
    inf.readEoln();
    
    sumNM += n * m;
    ensuref(sumNM <= MAXSUM, "Sum of n * m is greater than expected");

    a.clear();
    used.clear();
    for (int i = 0; i < n; ++i) {
        a.push_back(inf.readWord(format("[\\.#sf]{%d}", m).c_str(), "c_i"));
        used.push_back(std::vector<bool>(m, false));
        inf.readEoln();
    }

    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') {
                ensuref(sx == -1 && sy == -1, "Entrance cell is not unique");
                sx = i;
                sy = j;
            }
            if (a[i][j] == 'f') {
                ensuref(tx == -1 && ty == -1, "Exit cell is not unique");
                tx = i;
                ty = j;
            }
        }
    }

    ensuref(sx != -1 && sy != -1, "There is no entrance cell");
    ensuref(tx != -1 && ty != -1, "There is no exit cell");

    dfs(sx, sy);
    ensuref(used[tx][ty], "There is no path to the exit cell");
}

int main(int argc, char** argv) {
    registerValidation(argc, argv);

    int t = inf.readInt(1, MAXT, "t");
    inf.readEoln();
    
    for (int i = 1; i <= t; ++i) {
        setTestCase(i);
        readTestCase();
    }
    
    inf.readEof();

    return 0;
}
