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

typedef long long ll;
const ll mod = 998244353;

ll fWp[1005][1005], fWs[1005][1005], resW[1005];
ll fEp[1005][1005], fEs[1005][1005], resE[1005];
ll fNp[1005][1005], fNs[1005][1005], resN[1005];
ll fSp[1005][1005], fSs[1005][1005], resS[1005];
char s[1005][1005];
int limW[1005][2], limE[1005][2], limN[1005][2], limS[1005][2];
bool canc[1005], canr[1005];
ll hc[1005][2], hr[1005][2];

ll add(ll x, ll y) { return (x += y) >= mod ? x - mod : x; }

ll fpow(ll a, ll b)
{
    ll ans = 1;
    while (b)
    {
        if (b & 1) ans = ans * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return ans;
}

void work()
{
    int n, m; cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> s[i] + 1;

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
        {
            if (s[i][j] == '?') continue;
            if (s[i][j] == 'N')
            {
                int x = i;
                while (x > 1 && s[x - 1][j] == '?') s[x - 1][j] = 'N', x--;
                if (x > 1 && s[x - 1][j] != 'N') return cout << "0\n", void();
            }
            if (s[i][j] == 'S')
            {
                int x = i;
                while (x < n && s[x + 1][j] == '?') s[x + 1][j] = 'S', x++;
                if (x < n && s[x + 1][j] != 'S') return cout << "0\n", void();
            }
            if (s[i][j] == 'W')
            {
                int x = j;
                while (x > 1 && s[i][x - 1] == '?') s[i][x - 1] = 'W', x--;
                if (x > 1 && s[i][x - 1] != 'W') return cout << "0\n", void();
            }
            if (s[i][j] == 'E')
            {
                int x = j;
                while (x < m && s[i][x + 1] == '?') s[i][x + 1] = 'E', x++;
                if (x < m && s[i][x + 1] != 'E') return cout << "0\n", void();
            }
        }

    for (int i = 1; i <= max(n, m); i++) canc[i] = canr[i] = 0;
    hc[0][0] = hr[0][0] = hc[m + 1][1] = hr[n + 1][1] = 1;
    for (int i = 1; i <= m; i++)
    {
        limN[i][0] = 0, limN[i][1] = m;
        for (int j = 1; j <= n; j++)
            if (s[j][i] == 'N') limN[i][0] = max(limN[i][0], j);
            else if (s[j][i] != '?') limN[i][1] = min(limN[i][1], j - 1);
        if (limN[i][0] > limN[i][1]) return cout << "0\n", void();
        limS[i][0] = 0, limS[i][1] = m;
        for (int j = 1; j <= n; j++)
            if (s[n - j + 1][i] == 'S') limS[i][0] = max(limS[i][0], j);
            else if (s[n - j + 1][i] != '?') limS[i][1] = min(limS[i][1], j - 1);
        if (limS[i][0] > limS[i][1]) return cout << "0\n", void();
        if (limN[i][0] + limS[i][0] > n) return cout << "0\n", void();
        
        bool F = 1;
        for (int j = 1; j <= n; j++) F &= (s[j][i] != 'W' && s[j][i] != 'E');
        if (!F) hc[i][0] = hc[i - 1][1] = 1, canc[i] = 1;
        else hc[i][0] = hc[i - 1][1] = n - limN[i][0] - limS[i][0] + 1;
    }
    for (int i = 1; i <= n; i++)
    {
        limW[i][0] = 0, limW[i][1] = n;
        for (int j = 1; j <= m; j++)
            if (s[i][j] == 'W') limW[i][0] = max(limW[i][0], j);
            else if (s[i][j] != '?') limW[i][1] = min(limW[i][1], j - 1);
        if (limW[i][0] > limW[i][1]) return cout << "0\n", void();
        limE[i][0] = 0, limE[i][1] = n;
        for (int j = 1; j <= m; j++)
            if (s[i][m - j + 1] == 'E') limE[i][0] = max(limE[i][0], j);
            else if (s[i][m - j + 1] != '?') limE[i][1] = min(limE[i][1], j - 1);
        if (limE[i][0] > limE[i][1]) return cout << "0\n", void();
        if (limW[i][0] + limE[i][0] > m) return cout << "0\n", void();

        bool F = 1;
        for (int j = 1; j <= m; j++) F &= (s[i][j] != 'N' && s[i][j] != 'S');
        if (!F) hr[i][0] = hr[i - 1][1] = 1, canr[i] = 1;
        else hr[i][0] = hr[i - 1][1] = m - limW[i][0] - limE[i][0] + 1;
    }

    for (int i = 1; i <= n; i++) hr[i][0] = hr[i - 1][0] * hr[i][0] % mod; hr[n][1] = fpow(hr[n][0], mod - 2);
    for (int i = n - 1; ~i; i--) hr[i][1] = hr[i + 1][1] * hr[i][1] % mod;
    for (int i = 1; i <= m; i++) hc[i][0] = hc[i - 1][0] * hc[i][0] % mod; hc[m][1] = fpow(hc[m][0], mod - 2);
    for (int i = m - 1; ~i; i--) hc[i][1] = hc[i + 1][1] * hc[i][1] % mod;

    for (int i = 0; i <= n; i++) fNp[0][i] = fSp[0][i] = 1;
    for (int i = 1; i <= m; i++)
    {
        for (int j = 0; j < limN[i][0]; j++) fNp[i][j] = 0;
        for (int j = limN[i][0]; j <= limN[i][1]; j++) fNp[i][j] = add(fNp[i][j - 1], fNp[i - 1][j]);
        for (int j = limN[i][1] + 1; j <= n; j++) fNp[i][j] = fNp[i][j - 1];

        for (int j = 0; j < limS[i][0]; j++) fSp[i][j] = 0;
        for (int j = limS[i][0]; j <= limS[i][1]; j++) fSp[i][j] = add(fSp[i][j - 1], fSp[i - 1][j]);
        for (int j = limS[i][1] + 1; j <= n; j++) fSp[i][j] = fSp[i][j - 1];
    }

    for (int i = 0; i <= n; i++) fNs[m + 1][i] = fSs[m + 1][i] = 1;
    for (int i = m; i; i--)
    {
        for (int j = 0; j < limN[i][0]; j++) fNs[i][j] = 0;
        for (int j = limN[i][0]; j <= limN[i][1]; j++) fNs[i][j] = add(fNs[i][j - 1], fNs[i + 1][j]);
        for (int j = limN[i][1] + 1; j <= n; j++) fNs[i][j] = fNs[i][j - 1];

        for (int j = 0; j < limS[i][0]; j++) fSs[i][j] = 0;
        for (int j = limS[i][0]; j <= limS[i][1]; j++) fSs[i][j] = add(fSs[i][j - 1], fSs[i + 1][j]);
        for (int j = limS[i][1] + 1; j <= n; j++) fSs[i][j] = fSs[i][j - 1];
    }

    for (int i = 0; i <= m; i++) fWp[0][i] = fEp[0][i] = 1;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 0; j < limW[i][0]; j++) fWp[i][j] = 0;
        for (int j = limW[i][0]; j <= limW[i][1]; j++) fWp[i][j] = add(fWp[i][j - 1], fWp[i - 1][j]);
        for (int j = limW[i][1] + 1; j <= n; j++) fWp[i][j] = fWp[i][j - 1];

        for (int j = 0; j < limE[i][0]; j++) fEp[i][j] = 0;
        for (int j = limE[i][0]; j <= limE[i][1]; j++) fEp[i][j] = add(fEp[i][j - 1], fEp[i - 1][j]);
        for (int j = limE[i][1] + 1; j <= n; j++) fEp[i][j] = fEp[i][j - 1];
    }

    for (int i = 0; i <= m; i++) fWs[n + 1][i] = fEs[n + 1][i] = 1;
    for (int i = n; i; i--)
    {
        for (int j = 0; j < limW[i][0]; j++) fWs[i][j] = 0;
        for (int j = limW[i][0]; j <= limW[i][1]; j++) fWs[i][j] = add(fWs[i][j - 1], fWs[i + 1][j]);
        for (int j = limW[i][1] + 1; j <= n; j++) fWs[i][j] = fWs[i][j - 1];

        for (int j = 0; j < limE[i][0]; j++) fEs[i][j] = 0;
        for (int j = limE[i][0]; j <= limE[i][1]; j++) fEs[i][j] = add(fEs[i][j - 1], fEs[i + 1][j]);
        for (int j = limE[i][1] + 1; j <= n; j++) fEs[i][j] = fEs[i][j - 1];
    }

    ll ans = 0;
    for (int i = 0; i <= n; i++)
    {
        if (!i) resN[i] = fNs[1][0], resS[i] = fSs[1][0];
        else
        {
            resN[i] = resS[i] = 0;
            for (int j = 1; j <= m; j++) if (limN[j][0] <= i && i <= limN[j][1]) (resN[i] += fNp[j - 1][i - 1] * fNs[j + 1][i]) %= mod;
            for (int j = 1; j <= m; j++) if (limS[j][0] <= i && i <= limS[j][1]) (resS[i] += fSp[j - 1][i - 1] * fSs[j + 1][i]) %= mod;
        }
        resS[i] = (resS[i - 1] + resS[i] * hr[n - i][0]) % mod;
    }
    int lst = (canr[n] ? n : n + 1);
    for (int i = n - 1; ~i; i--)
    {
        (ans += resN[i] * hr[i][1] % mod * (resS[n - i - 1] + mod - (lst == n + 1 ? 0 : resS[n - lst]))) %= mod;
        if (canr[i]) lst = i;
    }
    
    for (int i = 0; i <= m; i++)
    {
        if (!i) resW[i] = fWs[1][0], resE[i] = fEs[1][0];
        else
        {
            resW[i] = resE[i] = 0;
            for (int j = 1; j <= n; j++) if (limW[j][0] <= i && i <= limW[j][1]) (resW[i] += fWp[j - 1][i - 1] * fWs[j + 1][i]) %= mod;
            for (int j = 1; j <= n; j++) if (limE[j][0] <= i && i <= limE[j][1]) (resE[i] += fEp[j - 1][i - 1] * fEs[j + 1][i]) %= mod;
        }
        resE[i] = (resE[i - 1] + resE[i] * hc[m - i][0]) % mod;
    }
    lst = (canc[m] ? m : m + 1);
    for (int i = m - 1; ~i; i--)
    {
        (ans += resW[i] * hc[i][1] % mod * (resE[m - i - 1] + mod - (lst == m + 1 ? 0 : resE[m - lst]))) %= mod;
        if (canc[i]) lst = i;
    }

    for (int x = 1; x < n; x++)
    {
        ll sum = 0;
        for (int i = m; i; i--)
        {
            if (limN[i][0] <= n - x && n - x <= limN[i][1]) (ans += sum * fNp[i - 1][n - x] % mod * fNs[i + 1][n - x - 1]) %= mod;
            if (limS[i][0] <= x && x <= limS[i][1]) (sum += fSp[i - 1][x - 1] * fSs[i + 1][x]) %= mod;
        }
        sum = 0;
        for (int i = 1; i <= m; i++)
        {
            if (limN[i][0] <= n - x && n - x <= limN[i][1]) (ans += sum * fNp[i - 1][n - x - 1] % mod * fNs[i + 1][n - x]) %= mod;
            if (limS[i][0] <= x && x <= limS[i][1]) (sum += fSp[i - 1][x] * fSs[i + 1][x - 1]) %= mod;
        }
    }

    for (int x = 1; x < m; x++)
    {
        ll sum = 0;
        for (int i = 1; i < n; i++)
        {
            if (limW[i][0] <= m - x && m - x <= limW[i][1]) (ans += sum * fWp[i][m - x - 1] % mod * fWs[i + 2][m - x]) %= mod;
            if (limE[i][0] <= x && x <= limE[i][1]) (sum += fEp[i - 1][x] * fEs[i + 1][x - 1]) %= mod;
        }
        sum = 0;
        for (int i = n; i > 1; i--)
        {
            if (limW[i][0] <= m - x && m - x <= limW[i][1]) (ans += sum * fWp[i - 2][m - x] % mod * fWs[i][m - x - 1]) %= mod;
            if (limE[i][0] <= x && x <= limE[i][1]) (sum += fEp[i - 1][x - 1] * fEs[i + 1][x]) %= mod;
        }
    }
    cout << ans << "\n";
}

int main()
{
    ios::sync_with_stdio(false), cin.tie(0);

    int T; cin >> T;
    while (T--) work();
    return 0;
}