#include <bits/stdc++.h>

using namespace std;

#define rep(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define rrep(i, a, b) for (int i = (int)(b)-1; i >= (int)(a); i--)
#define ALL(v) (v).begin(), (v).end()
#define UNIQUE(v) sort(ALL(v)), (v).erase(unique(ALL(v)), (v).end())
#define SZ(v) (int)v.size()
#define MIN(v) *min_element(ALL(v))
#define MAX(v) *max_element(ALL(v))
#define LB(v, x) int(lower_bound(ALL(v), (x)) - (v).begin())
#define UB(v, x) int(upper_bound(ALL(v), (x)) - (v).begin())

using uint = unsigned int;
using ll = long long int;
using ull = unsigned long long;
using i128 = __int128_t;
using u128 = __uint128_t;
const int inf = 0x3fffffff;
const ll INF = 0x1fffffffffffffff;

template <typename T> inline bool chmax(T &a, T b) {
    if (a < b) {
        a = b;
        return 1;
    }
    return 0;
}
template <typename T> inline bool chmin(T &a, T b) {
    if (a > b) {
        a = b;
        return 1;
    }
    return 0;
}
template <typename T, typename U> T ceil(T x, U y) {
    assert(y != 0);
    if (y < 0)
        x = -x, y = -y;
    return (x > 0 ? (x + y - 1) / y : x / y);
}
template <typename T, typename U> T floor(T x, U y) {
    assert(y != 0);
    if (y < 0)
        x = -x, y = -y;
    return (x > 0 ? x / y : (x - y + 1) / y);
}
template <typename T> int popcnt(T x) {
    return __builtin_popcountll(x);
}
template <typename T> int topbit(T x) {
    return (x == 0 ? -1 : 63 - __builtin_clzll(x));
}
template <typename T> int lowbit(T x) {
    return (x == 0 ? -1 : __builtin_ctzll(x));
}

template <class T, class U>
ostream &operator<<(ostream &os, const pair<T, U> &p) {
    os << "P(" << p.first << ", " << p.second << ")";
    return os;
}
template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec) {
    os << "{";
    for (int i = 0; i < vec.size(); i++) {
        os << vec[i] << (i + 1 == vec.size() ? "" : ", ");
    }
    os << "}";
    return os;
}
template <typename T, typename U>
ostream &operator<<(ostream &os, const map<T, U> &map_var) {
    os << "{";
    for (auto itr = map_var.begin(); itr != map_var.end(); itr++) {
        os << "(" << itr->first << ", " << itr->second << ")";
        itr++;
        if (itr != map_var.end())
            os << ", ";
        itr--;
    }
    os << "}";
    return os;
}
template <typename T> ostream &operator<<(ostream &os, const set<T> &set_var) {
    os << "{";
    for (auto itr = set_var.begin(); itr != set_var.end(); itr++) {
        os << *itr;
        ++itr;
        if (itr != set_var.end())
            os << ", ";
        itr--;
    }
    os << "}";
    return os;
}
#ifdef LOCAL
#define show(...) _show(0, #__VA_ARGS__, __VA_ARGS__)
#else
#define show(...) true
#endif
template <typename T> void _show(int i, T name) {
    cerr << '\n';
}
template <typename T1, typename T2, typename... T3>
void _show(int i, const T1 &a, const T2 &b, const T3 &...c) {
    for (; a[i] != ',' && a[i] != '\0'; i++)
        cerr << a[i];
    cerr << ":" << b << " ";
    _show(i + 1, a, c...);
}

/**
 * @brief template
 */

template <unsigned mod = 1000000007> struct fp {
    unsigned v;
    static constexpr int get_mod() {
        return mod;
    }
    constexpr unsigned inv() const {
        assert(v != 0);
        int x = v, y = mod, p = 1, q = 0, t = 0, tmp = 0;
        while (y > 0) {
            t = x / y;
            x -= t * y, p -= t * q;
            tmp = x, x = y, y = tmp;
            tmp = p, p = q, q = tmp;
        }
        if (p < 0)
            p += mod;
        return p;
    }
    constexpr fp(ll x = 0) : v(x >= 0 ? x % mod : (mod - (-x) % mod) % mod) {}
    fp operator-() const {
        return fp() - *this;
    }
    fp pow(ull t) {
        fp res = 1, b = *this;
        while (t) {
            if (t & 1)
                res *= b;
            b *= b;
            t >>= 1;
        }
        return res;
    }
    fp &operator+=(const fp &x) {
        if ((v += x.v) >= mod)
            v -= mod;
        return *this;
    }
    fp &operator-=(const fp &x) {
        if ((v += mod - x.v) >= mod)
            v -= mod;
        return *this;
    }
    fp &operator*=(const fp &x) {
        v = ull(v) * x.v % mod;
        return *this;
    }
    fp &operator/=(const fp &x) {
        v = ull(v) * x.inv() % mod;
        return *this;
    }
    fp operator+(const fp &x) const {
        return fp(*this) += x;
    }
    fp operator-(const fp &x) const {
        return fp(*this) -= x;
    }
    fp operator*(const fp &x) const {
        return fp(*this) *= x;
    }
    fp operator/(const fp &x) const {
        return fp(*this) /= x;
    }
    bool operator==(const fp &x) const {
        return v == x.v;
    }
    bool operator!=(const fp &x) const {
        return v != x.v;
    }
    friend istream &operator>>(istream &is, fp &x) {
        return is >> x.v;
    }
    friend ostream &operator<<(ostream &os, const fp &x) {
        return os << x.v;
    }
};

// template <unsigned mod> void rd(fp<mod> &x) {
//     fastio::rd(x.v);
// }
// template <unsigned mod> void wt(fp<mod> x) {
//     fastio::wt(x.v);
// }

template <typename T> T Inv(ll n) {
    static const int md = T::get_mod();
    static vector<T> buf({0, 1});
    assert(n > 0);
    n %= md;
    while (SZ(buf) <= n) {
        int k = SZ(buf), q = (md + k - 1) / k;
        buf.push_back(buf[k * q - md] * q);
    }
    return buf[n];
}

template <typename T> T Fact(ll n, bool inv = 0) {
    static const int md = T::get_mod();
    static vector<T> buf({1, 1}), ibuf({1, 1});
    assert(n >= 0 and n < md);
    while (SZ(buf) <= n) {
        buf.push_back(buf.back() * SZ(buf));
        ibuf.push_back(ibuf.back() * Inv<T>(SZ(ibuf)));
    }
    return inv ? ibuf[n] : buf[n];
}

template <typename T> T nPr(int n, int r, bool inv = 0) {
    if (n < 0 || n < r || r < 0)
        return 0;
    return Fact<T>(n, inv) * Fact<T>(n - r, inv ^ 1);
}
template <typename T> T nCr(int n, int r, bool inv = 0) {
    if (n < 0 || n < r || r < 0)
        return 0;
    return Fact<T>(n, inv) * Fact<T>(r, inv ^ 1) * Fact<T>(n - r, inv ^ 1);
}
template <typename T> T nHr(int n, int r, bool inv = 0) {
    return nCr<T>(n + r - 1, r, inv);
}

/**
 * @brief Modint
 */

using Fp = fp<998244353>;

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

void Solve() {
    int N, M;
    cin >> N >> M;
    vector<vector<int>> A(N, vector<int>(M, -1));
    vector<string> S(N);
    rep(i,0,N) cin >> S[i];
    {
        rep(i,0,N) {
            rep(j,0,M) {
                if (S[i][j] == 'N') A[i][j] = 0;
                if (S[i][j] == 'W') A[i][j] = 1;
                if (S[i][j] == 'S') A[i][j] = 2;
                if (S[i][j] == 'E') A[i][j] = 3;
            }
        }
    }
    vector<vector<vector<bool>>> B(N, vector<vector<bool>>(M, vector<bool>(4,true)));
    auto dox = [&](int i, int j, int d) -> void {
        rep(k,0,4) if (k != d) B[i][j][k] = false;
    };
    rep(i,0,N) {
        rep(j,0,M) {
            if (A[i][j] >= 0) {
                rep(k,0,4) if (k != A[i][j]) B[i][j][k] = false;
            }
        }
    }
    rep(i,0,N) {
        bool canw = true, doe = false;
        rep(j,0,M) {
            if (S[i][j] == 'E') doe = true;
            if (S[i][j] != 'W' && S[i][j] != '?') canw = false;
            if (doe) dox(i,j,3);
            if (!canw) B[i][j][1] = false;
        }
    }
    rep(i,0,N) {
        bool cane = true, dow = false;
        rrep(j,0,M) {
            if (S[i][j] == 'W') dow = true;
            if (S[i][j] != 'E' && S[i][j] != '?') cane = false;
            if (dow) dox(i,j,1);
            if (!cane) B[i][j][3] = false;
        }
    }
    rep(j,0,M) {
        bool cann = true, dos = false;
        rep(i,0,N) {
            if (S[i][j] == 'S') dos = true;
            if (S[i][j] != 'N' && S[i][j] != '?') cann = false;
            if (dos) dox(i,j,2);
            if (!cann) B[i][j][0] = false;
        }
    }
    rep(j,0,M) {
        bool cans = true, don = false;
        rrep(i,0,N) {
            if (S[i][j] == 'N') don = true;
            if (S[i][j] != 'S' && S[i][j] != '?') cans = false;
            if (don) dox(i,j,0);
            if (!cans) B[i][j][2] = false;
        }
    }
    rep(i,0,N) {
        rep(j,0,M) {
            bool check = false;
            rep(k,0,4) if (B[i][j][k]) check = true;
            if (!check) {
                cout << 0 << endl;
                return;
            }
        }
    }
    auto isValid = [&](int i, int j, int d) -> bool {
        if (0 <= i && i < N && 0 <= j && j < M && !B[i][j][d]) return false;
        else return true;
    };
    vector<vector<Fp>> NW(N+1, vector<Fp>(M+1, 0));
    NW[0][0] = 1;
    rep(i,0,N+1) {
        rep(j,0,M+1) {
            if (i < N) {
                if (isValid(i,j-1,1) && isValid(i,j,0)) NW[i+1][j] += NW[i][j];
            }
            if (j < M) {
                if (isValid(i-1,j,0) && isValid(i,j,1)) NW[i][j+1] += NW[i][j];
            }
        }
    }
    vector<vector<Fp>> WS(N+1, vector<Fp>(M+1, 0));
    WS[N][0] = 1;
    rrep(i,0,N+1) {
        rep(j,0,M+1) {
            if (i > 0) {
                if (isValid(i-1,j-1,1) && isValid(i-1,j,2)) WS[i-1][j] += WS[i][j];
            }
            if (j < M) {
                if (isValid(i-1,j,1) && isValid(i,j,2)) WS[i][j+1] += WS[i][j];
            }
        }
    }
    vector<vector<Fp>> SE(N+1, vector<Fp>(M+1, 0));
    SE[N][M] = 1;
    rrep(i,0,N+1) {
        rrep(j,0,M+1) {
            if (i > 0) {
                if (isValid(i-1,j-1,2) && isValid(i-1,j,3)) SE[i-1][j] += SE[i][j];
            }
            if (j > 0) {
                if (isValid(i-1,j-1,3) && isValid(i,j-1,2)) SE[i][j-1] += SE[i][j];
            }
        }
    }
    vector<vector<Fp>> EN(N+1, vector<Fp>(M+1, 0));
    EN[0][M] = 1;
    rep(i,0,N+1) {
        rrep(j,0,M+1) {
            if (i < N) {
                if (isValid(i,j-1,0) && isValid(i,j,3)) EN[i+1][j] += EN[i][j];
            }
            if (j > 0) {
                if (isValid(i-1,j-1,0) && isValid(i,j-1,3)) EN[i][j-1] += EN[i][j];
            }
        }
    }
    Fp ANS = 0;
    //all are adjacent at a corner
    {
        rep(i,1,N) {
            rep(j,1,M) {
                if (isValid(i-1,j-1,0) && isValid(i,j-1,1) && isValid(i,j,2) && isValid(i-1,j,3)) {
                    ANS += NW[i][j-1] * WS[i+1][j] * SE[i][j+1] * EN[i-1][j];
                }
                if (isValid(i-1,j,0) && isValid(i-1,j-1,1) && isValid(i,j-1,2) && isValid(i,j,3)) {
                    ANS += NW[i-1][j] * WS[i][j-1] * SE[i+1][j] * EN[i][j+1];
                }
            }
        }
    }
    //cout << ANS << endl;
    //N and S are adjacent
    {
        vector<int> NC(M,N), SC(M,0);
        rep(i,0,N) {
            rep(j,0,M) {
                if (!B[i][j][0]) chmin(NC[j], i);
                if (!B[i][j][2]) chmax(SC[j], i+1);
            }
        }
        vector<Fp> Len(M);
        rep(i,0,M) {
            if (NC[i] < SC[i]) Len[i] = 0;
            else Len[i] = NC[i] - SC[i] + 1;
        }
        vector<Fp> WC(M+1,0), EC(M+1,0);
        {
            bool check = true;
            rep(i,0,N) {
                if (!B[i][0][0] && !B[i][0][2]) check = false;
            }
            if (check) WC[0] = 1;
        }
        {
            bool check = true;
            rep(i,0,N) {
                if (!B[i][M-1][0] && !B[i][M-1][2]) check = false;
            }
            if (check) EC[M] = 1;
        }
        rep(j,1,M+1) {
            vector<Fp> TmpN(N+1,0), TmpS(N+1,0);
            rep(i,0,N+1) {
                if (isValid(i-1,j-1,0) && isValid(i,j-1,1)) TmpN[i] = NW[i][j-1];
                if (isValid(i-1,j-1,1) && isValid(i,j-1,2)) TmpS[i] = WS[i][j-1];
            }
            Fp Cur = TmpN[0];
            rep(i,0,N) {
                if (!(isValid(i,j-1,1) && (isValid(i,j,0) || isValid(i,j,2)))) Cur = 0;
                WC[j] += Cur * TmpS[i+1];
                Cur += TmpN[i+1];
            }
        }
        rep(j,0,M) {
            vector<Fp> TmpN(N+1,0), TmpS(N+1,0);
            rep(i,0,N+1) {
                if (isValid(i-1,j,0) && isValid(i,j,3)) TmpN[i] = EN[i][j+1];
                if (isValid(i-1,j,3) && isValid(i,j,2)) TmpS[i] = SE[i][j+1];
            }
            Fp Cur = TmpN[0];
            rep(i,0,N) {
                if (!(isValid(i,j,3) && (isValid(i,j-1,0) || isValid(i,j-1,2)))) Cur = 0;
                EC[j] += Cur * TmpS[i+1];
                Cur += TmpN[i+1];
            }
        }
        rep(j,1,M) {
            vector<Fp> TmpNW(N+1,0), TmpSW(N+1,0);
            rep(i,0,N+1) {
                if (isValid(i-1,j-1,0) && isValid(i,j-1,1)) TmpNW[i] = NW[i][j-1];
                if (isValid(i-1,j-1,1) && isValid(i,j-1,2)) TmpSW[i] = WS[i][j-1];
            }
            vector<Fp> TmpNE(N+1,0), TmpSE(N+1,0);
            rep(i,0,N+1) {
                if (isValid(i-1,j,0) && isValid(i,j,3)) TmpNE[i] = EN[i][j+1];
                if (isValid(i-1,j,3) && isValid(i,j,2)) TmpSE[i] = SE[i][j+1];
            }
            {
                Fp Cur = 0;
                rep(i,1,N) {
                    ANS += Cur * TmpNE[i];
                    Cur += TmpSW[i];
                }
                Cur = 0;
                rep(i,1,N) {
                    ANS += Cur * TmpNW[i];
                    Cur += TmpSE[i];
                }
            }
        }
        {
            Fp Cur = WC[0];
            rep(i,0,M) {
                Cur *= Len[i];
                ANS += Cur * EC[i+1];
                Cur += WC[i+1];
            }
        }
    }
    //cout << ANS << endl;
    //W and E are adjacent
    {
        vector<int> WC(N,M), EC(N,0);
        rep(i,0,N) {
            rep(j,0,M) {
                if (!B[i][j][1]) chmin(WC[i], j);
                if (!B[i][j][3]) chmax(EC[i], j+1);
            }
        }
        vector<Fp> Len(N);
        rep(i,0,N) {
            if (WC[i] < EC[i]) Len[i] = 0;
            else Len[i] = WC[i] - EC[i] + 1;
        }
        vector<Fp> NC(N+1,0), SC(N+1,0);
        {
            bool check = true;
            rep(j,0,M) {
                if (!B[0][j][1] && !B[0][j][3]) check = false;
            }
            if (check) NC[0] = 1;
        }
        {
            bool check = true;
            rep(j,0,M) {
                if (!B[N-1][j][1] && !B[N-1][j][3]) check = false;
            }
            if (check) SC[N] = 1;
        }
        rep(i,1,N+1) {
            vector<Fp> TmpW(M+1,0), TmpE(M+1,0);
            rep(j,0,M+1) {
                if (isValid(i-1,j-1,1) && isValid(i-1,j,0)) TmpW[j] = NW[i-1][j];
                if (isValid(i-1,j-1,0) && isValid(i-1,j,3)) TmpE[j] = EN[i-1][j];
            }
            Fp Cur = TmpW[0];
            rep(j,0,M) {
                if (!(isValid(i-1,j,0) && (isValid(i,j,1) || isValid(i,j,3)))) Cur = 0;
                NC[i] += Cur * TmpE[j+1];
                Cur += TmpW[j+1];
            }
        }
        rep(i,0,N) {
            vector<Fp> TmpW(M+1,0), TmpE(M+1,0);
            rep(j,0,M+1) {
                if (isValid(i,j-1,1) && isValid(i,j,2)) TmpW[j] = WS[i+1][j];
                if (isValid(i,j-1,2) && isValid(i,j,3)) TmpE[j] = SE[i+1][j];
            }
            Fp Cur = TmpW[0];
            rep(j,0,M) {
                if (!(isValid(i,j,2) && (isValid(i-1,j,1) || isValid(i-1,j,3)))) Cur = 0;
                SC[i] += Cur * TmpE[j+1];
                Cur += TmpW[j+1];
            }
        }
        rep(i,1,N) {
            vector<Fp> TmpWN(M+1,0), TmpEN(M+1,0);
            rep(j,0,M+1) {
                if (isValid(i-1,j-1,1) && isValid(i-1,j,0)) TmpWN[j] = NW[i-1][j];
                if (isValid(i-1,j-1,0) && isValid(i-1,j,3)) TmpEN[j] = EN[i-1][j];
            }
            vector<Fp> TmpWS(M+1,0), TmpES(M+1,0);
            rep(j,0,M+1) {
                if (isValid(i,j-1,1) && isValid(i,j,2)) TmpWS[j] = WS[i+1][j];
                if (isValid(i,j-1,2) && isValid(i,j,3)) TmpES[j] = SE[i+1][j];
            }
            {
                Fp Cur = 0;
                rep(j,1,M) {
                    ANS += Cur * TmpWS[j];
                    Cur += TmpEN[j];
                }
                Cur = 0;
                rep(j,1,M) {
                    ANS += Cur * TmpWN[j];
                    Cur += TmpES[j];
                }
            }
        }
        {
            Fp Cur = NC[0];
            rep(i,0,N) {
                Cur *= Len[i];
                ANS += Cur * SC[i+1];
                Cur += NC[i+1];
            }
        }
    }
    cout << ANS << endl;

}

int main() {
    cin.tie(0);
    ios_base::sync_with_stdio(false);
int _;
cin >> _;
while(_--) {
    Solve();
}
}