#include<bits/stdc++.h>
using namespace std;
constexpr int N=1e3+5,mod=998244353;
int n,m;
string s[N];
inline void red(int&x){(x>=mod)&&(x-=mod);}
int ul[N][N],ur[N][N],dl[N][N],dr[N][N];
bool l[N][N],r[N][N],d[N][N],u[N][N];
int dp[N],tt[N];
inline void solve(){
    cin>>n>>m;
    s[1]=" "+string(m+2,'N');
    s[n+2]=" "+string(m+2,'S');
    for(int i=2;i<=n+1;i++) cin>>s[i],s[i]=" W"+s[i]+"E";
    n+=2;m+=2;
    for(int i=0;i<=n+1;i++)
    for(int j=0;j<=m+1;j++) l[i][j]=d[i][j]=r[i][j]=u[i][j]=0;
    for(int i=1;i<=n;i++) l[i][0]=r[i][m+1]=1;
    for(int i=1;i<=m;i++) u[0][i]=d[n+1][i]=1;
    for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){
        char c=s[i][j];
        l[i][j]=l[i][j-1]&(c=='W'||c=='?');
        u[i][j]=u[i-1][j]&(c=='N'||c=='?');
    }for(int i=n;i>=1;i--)for(int j=m;j>=1;j--){
        char c=s[i][j];
        r[i][j]=r[i][j+1]&(c=='E'||c=='?');
        d[i][j]=d[i+1][j]&(c=='S'||c=='?');
    }
    for(int i=0;i<=n;i++) ul[i][0]=1;
    for(int i=0;i<=m;i++) ul[0][i]=1;
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++) red(ul[i][j]=ul[i-1][j]*l[i][j]+ul[i][j-1]*u[i][j]);
    for(int i=0;i<=n;i++) ur[i][m]=1;
    for(int i=0;i<=m;i++) ur[0][i]=1;
    for(int i=1;i<=n;i++)
    for(int j=m-1;j>=0;j--) red(ur[i][j]=ur[i-1][j]*r[i][j+1]+ur[i][j+1]*u[i][j+1]);
    for(int i=0;i<=n;i++) dl[i][0]=1;
    for(int i=0;i<=m;i++) dl[n][i]=1;
    for(int i=n-1;i>=0;i--)
    for(int j=1;j<=m;j++) red(dl[i][j]=dl[i+1][j]*l[i+1][j]+dl[i][j-1]*d[i+1][j]);
    for(int i=0;i<=n;i++) dr[i][m]=1;
    for(int i=0;i<=m;i++) dr[n][i]=1;
    for(int i=n-1;i>=0;i--)
    for(int j=m-1;j>=0;j--) red(dr[i][j]=dr[i+1][j]*r[i+1][j+1]+dr[i][j+1]*d[i+1][j+1]);
    long long ans=0;
    memset(dp,0,sizeof dp);
    for(int j=1;j<=m;j++){
        int sum=0;
        for(int i=0;i<=n;i++) tt[i]=(u[i][j]&&d[i+1][j]?dp[i]:0);
        for(int i=1;i<n;i++) if(r[i][j+1]&&r[i+1][j+1]) ans+=tt[i]*1ll*ur[i-1][j]%mod*dr[i+1][j]%mod;
        for(int i=0;i<=n;i++){
            red(sum+=tt[i]);
            if(i&&l[i][j]&&d[i+1][j]) red(sum+=ul[i-1][j]*1ll*dl[i][j-1]%mod);
            dp[i]=sum;
            if(i<n&&r[i+1][j+1]&&u[i][j+1]) ans+=ur[i][j+1]*1ll*dr[i+1][j]%mod*sum%mod;
        }sum=0;
        for(int i=n;i>=0;i--){
            if(i<n&&u[i][j]&&l[i+1][j]) red(sum+=ul[i][j-1]*1ll*dl[i+1][j]%mod);
            red(dp[i]+=sum);red(sum+=tt[i]);
            if(i&&r[i][j+1]&&d[i+1][j+1]) ans+=ur[i-1][j]*1ll*dr[i][j+1]%mod*sum%mod;
        }
        for(int i=1;i<n;i++) if(l[i][j]&&l[i+1][j]) red(dp[i]+=ul[i-1][j]*1ll*dl[i+1][j]);
    }
    memset(dp,0,sizeof dp);
    for(int i=1;i<=n;i++){
        int sum=0;
        for(int j=0;j<=m;j++) tt[j]=(l[i][j]&&r[i][j+1]?dp[j]:0);
        for(int j=1;j<m;j++)if(d[i+1][j]&&d[i+1][j+1]) ans+=tt[j]*1ll*dl[i][j-1]%mod*dr[i][j+1]%mod;
        for(int j=0;j<=m;j++){
            red(sum+=tt[j]);
            if(j<m&&l[i+1][j]&&d[i+1][j+1]) ans+=dl[i+1][j]*1ll*dr[i][j+1]%mod*sum%mod;
            if(j&&u[i][j]&&r[i][j+1]) red(sum+=ul[i][j-1]*1ll*ur[i-1][j]%mod);
            dp[j]=sum;
        }sum=0;
        for(int j=m;j>=0;j--){
            if(j&&d[i+1][j]&&r[i+1][j+1]) ans+=dl[i][j-1]*1ll*dr[i+1][j]%mod*(sum+tt[j])%mod;
            if(j<m&&l[i][j]&&u[i][j+1]) red(sum+=ul[i-1][j]*1ll*ur[i][j+1]%mod);
            red(dp[j]+=sum);
            red(sum+=tt[j]);
        }
        for(int j=1;j<m;j++) if(u[i][j]&&u[i][j+1]) red(dp[j]+=ul[i][j-1]*1ll*ur[i][j+1]);
    }
    cout<<ans%mod<<'\n';
}
int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int T;cin>>T;
    while(T--) solve();
}