#include<bits/stdc++.h>

using namespace std;
#define rep2(i, j, k) for(ll i=ll(j);i<ll(k);i++)
#define rep(i, k) rep2(i,0,k)
#define rrep2(i, j, k) for(ll i=ll(j)-1;i>=ll(k);i--)
#define rrep(i, j) rrep2(i,j,0)
#define SZ(a) ll(a.size())
#define eb emplace_back
#define all(a) a.begin(),a.end()
using ll = long long;
using vl = vector<ll>;
using vvl = vector<vl>;
using P = pair<ll, ll>;
using vp = vector<P>;
using vvp = vector<vp>;
const ll inf = LLONG_MAX / 4;

template<class T>
bool chmin(T &a, T b) { return a > b ? a = b, 1 : 0; }

template<class T>
bool chmax(T &a, T b) { return a < b ? a = b, 1 : 0; }

const int mod = 998244353;

struct mint {
    ll x;

    mint(ll x = 0) : x(((x % mod) + mod) % mod) {}

    mint &operator+=(const mint &a) {
        if ((x += a.x) >= mod) x -= mod;
        return *this;
    }

    mint &operator-=(const mint &a) {
        if ((x += mod - a.x) >= mod) x -= mod;
        return *this;
    }

    mint &operator*=(const mint &a) {
        (x *= a.x) %= mod;
        return *this;
    }

    mint operator+(const mint &a) { return mint(*this) += a; }

    mint operator-(const mint &a) { return mint(*this) -= a; }

    mint operator*(const mint &a) { return mint(*this) *= a; }
};

mint lu[1010][1010];
mint ld[1010][1010];
mint ru[1010][1010];
mint rd[1010][1010];

void solve() {
    int n, m;
    cin >> n >> m;
    vector<string> s(n);
    rep(i, n) cin >> s[i];
    mint ans;
    rep(t, 2) {
        vl N(m), S(m, n), W(n), E(n, m);
        vl Nc(m), Sc(m, n), Wc(n), Ec(n, m);
        rep(i, n) rep(j, m) {
                if (s[i][j] == 'N') chmax(N[j], i + 1);
                if (s[i][j] == 'S') chmin(S[j], i);
                if (s[i][j] == 'W') chmax(W[i], j + 1);
                if (s[i][j] == 'E') chmin(E[i], j);
            }
        bool ok = true;
        rep(i, n) {
            while (Wc[i] < m and (s[i][Wc[i]] == 'W' or s[i][Wc[i]] == '?')) ++Wc[i];
            while (Ec[i] and (s[i][Ec[i] - 1] == 'E' or s[i][Ec[i] - 1] == '?')) --Ec[i];
            if (W[i] > Wc[i] or E[i] < Ec[i]) ok = false;
        }
        rep(i, m) {
            while (Nc[i] < n and (s[Nc[i]][i] == 'N' or s[Nc[i]][i] == '?')) ++Nc[i];
            while (Sc[i] and (s[Sc[i] - 1][i] == 'S' or s[Sc[i] - 1][i] == '?')) --Sc[i];
            if (N[i] > Nc[i] or S[i] < Sc[i]) ok = false;
        }
        if (!ok) {
            cout << 0 << '\n';
            return;
        }
//        cout << "t: " << t << endl;
//        rep(i, m) printf("%lld %lld %lld %lld %lld\n", i, N[i], Nc[i], S[i], Sc[i]);
//        rep(i, n) printf("%lld %lld %lld %lld %lld\n", i, W[i], Wc[i], E[i], Ec[i]);
        rep(i, n + 1) rep(j, m + 1) {
                if (!i and !j) {
                    lu[i][j] = 1;
                    continue;
                }
                lu[i][j] = 0;
                if (i and W[i - 1] <= j and j <= Wc[i - 1]) lu[i][j] += lu[i - 1][j];
                if (j and N[j - 1] <= i and i <= Nc[j - 1]) lu[i][j] += lu[i][j - 1];
            }
        rrep(i, n + 1) rep(j, m + 1) {
                if (i == n and !j) {
                    ld[i][j] = 1;
                    continue;
                }
                ld[i][j] = 0;
                if (i < n and W[i] <= j and j <= Wc[i]) ld[i][j] += ld[i + 1][j];
                if (j and Sc[j - 1] <= i and i <= S[j - 1]) ld[i][j] += ld[i][j - 1];
            }
        rep(i, n + 1) rrep(j, m + 1) {
                if (!i and j == m) {
                    ru[i][j] = 1;
                    continue;
                }
                ru[i][j] = 0;
                if (i and Ec[i - 1] <= j and j <= E[i - 1]) ru[i][j] += ru[i - 1][j];
                if (j < m and N[j] <= i and i <= Nc[j]) ru[i][j] += ru[i][j + 1];
            }
        rrep(i, n + 1) rrep(j, m + 1) {
                if (i == n and j == m) {
                    rd[i][j] = 1;
                    continue;
                }
                rd[i][j] = 0;
                if (i < n and Ec[i] <= j and j <= E[i]) rd[i][j] += rd[i + 1][j];
                if (j < m and Sc[j] <= i and i <= S[j]) rd[i][j] += rd[i][j + 1];
            }
        vector<mint> lc(m + 1), rc(m + 1);
        lc[0] = rc[m] = 1;
        rep(j, m + 1) {
            if (j)
                rep(i, n) {
                    if (!(W[i] <= j and j <= Wc[i])) continue;
                    if (!(N[j - 1] <= i and i <= Nc[j - 1])) continue;
                    mint now = lu[i][j - 1];
                    now *= ld[i + 1][j];
                    lc[j] += now;
                }
            if (j < m)
                rep(i, n) {
                    if (!(Ec[i] <= j and j <= E[i])) continue;
                    if (!(N[j] <= i and i <= Nc[j])) continue;
                    mint now = ru[i][j + 1];
                    now *= rd[i + 1][j];
                    rc[j] += now;
                }
//            printf("%lld %lld %lld\n", j, lc[j].x, rc[j].x);
        }
        rep(l, m) {
            mint cur = 1;
            rep2(r, l + 1, m + 1) {
                assert(N[r - 1] <= S[r - 1]);
                if (Nc[r - 1] != S[r - 1]) break;
                assert(Sc[r - 1] == N[r - 1]);
                cur *= S[r - 1] - N[r - 1] + 1;
                ans += cur * lc[l] * rc[r];
            }
        }
//        cout << ans.x << endl;
        rep2(i, 1, n) {
            rep2(j, 1, m) rep2(k, j, m) {
                    if (t and j == k) continue;
                    if (!(N[j - 1] <= i and i <= Nc[j - 1])) continue;
                    if (!(Ec[i - 1] <= j and j <= E[i - 1])) continue;
                    if (!(Sc[k] <= i and i <= S[k])) continue;
                    if (!(W[i] <= k and k <= Wc[i])) continue;
                    mint now = 1;
                    now *= lu[i][j - 1] * ru[i - 1][j];
                    now *= rd[i][k + 1] * ld[i + 1][k];
                    ans += now;
//                    printf("%lld %lld %lld %lld\n", i, j, k, now.x);
                }
            rep2(j, 1, m) rep2(k, j, m) {
                    if (t and j == k) continue;
                    if (!(Sc[j - 1] <= i and i <= S[j - 1])) continue;
                    if (!(Ec[i] <= j and j <= E[i])) continue;
                    if (!(N[k] <= i and i <= Nc[k])) continue;
                    if (!(W[i - 1] <= k and k <= Wc[i - 1])) continue;
                    mint now = 1;
                    now *= ld[i][j - 1] * rd[i + 1][j];
                    now *= ru[i][k + 1] * lu[i - 1][k];
                    ans += now;
//                    printf("%lld %lld %lld %lld\n", i, j, k, now.x);
                }
        }
//        cout << ans.x << endl;
        vector<string> ns(m, string(n, ' '));
        rep(i, n) rep(j, m) {
                char c = s[i][j];
                if (c == 'W' or c == 'N') c = 'W' + 'N' - c;
                if (c == 'S' or c == 'E') c = 'S' + 'E' - c;
                ns[j][i] = c;
            }
        swap(s, ns);
        swap(n, m);
    }
    cout << ans.x << '\n';
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int t;
    cin >> t;
    while (t--) solve();
}