#include<bits/stdc++.h>
using namespace std;
using i64=long long;
const i64 P=998244353;
int T,n,m;
i64 w1[1005][1005],w2[1005][1005],w3[1005];
i64 e1[1005][1005],e2[1005][1005],e3[1005];
i64 n1[1005][1005],n2[1005][1005],n3[1005];
i64 s1[1005][1005],s2[1005][1005],s3[1005];
char s[1005][1005];
int tagw[1005][2],tage[1005][2],tagn[1005][2],tags[1005][2];
bool tag1[1005],tag2[1005];
i64 hc[1005][2],hr[1005][2];
int fadd(int x,int y){
return (x+y>=P?x+y-P:x+y);
}
i64 power(i64 aa,i64 nn){
i64 ret=1;
for(;nn;nn>>=1,aa=aa*aa%P) if(nn&1) ret=ret*aa%P;
return ret;
}
void solve(){
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++) tag1[i]=tag2[i]=0;
hc[0][0]=hr[0][0]=hc[m+1][1]=hr[n+1][1]=1;
for(int i=1;i<=m;i++){
tagn[i][0]=0,tagn[i][1]=n;
for(int j=1;j<=n;j++)
if(s[j][i]=='N') tagn[i][0]=max(tagn[i][0],j);
else if(s[j][i]!='?') tagn[i][1]=min(tagn[i][1],j-1);
if(tagn[i][0]>tagn[i][1]) return cout<<"0\n",void();
tags[i][0]=0,tags[i][1]=n;
for(int j=1;j<=n;j++)
if(s[n-j+1][i]=='S') tags[i][0]=max(tags[i][0],j);
else if(s[n-j+1][i]!='?') tags[i][1]=min(tags[i][1],j-1);
if(tags[i][0]>tags[i][1]) return cout<<"0\n",void();
if(tagn[i][0]+tags[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,tag1[i]=1;
else hc[i][0]=hc[i-1][1]=n-tagn[i][0]-tags[i][0]+1;
}
for(int i=1;i<=n;i++){
tagw[i][0]=0,tagw[i][1]=m;
for(int j=1;j<=m;j++)
if(s[i][j]=='W') tagw[i][0]=max(tagw[i][0],j);
else if(s[i][j]!='?') tagw[i][1]=min(tagw[i][1],j-1);
if(tagw[i][0]>tagw[i][1]) return cout<<"0\n",void();
tage[i][0]=0,tage[i][1]=m;
for(int j=1;j<=m;j++)
if(s[i][m-j+1]=='E') tage[i][0]=max(tage[i][0],j);
else if(s[i][m-j+1]!='?') tage[i][1]=min(tage[i][1],j-1);
if(tage[i][0]>tage[i][1]) return cout<<"0\n",void();
if(tagw[i][0]+tage[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,tag2[i]=1;
else hr[i][0]=hr[i-1][1]=m-tagw[i][0]-tage[i][0]+1;
}
for(int i=1;i<=n;i++) hr[i][0]=hr[i-1][0]*hr[i][0]%P;
hr[n][1]=power(hr[n][0],P-2);
for(int i=n-1;~i;i--) hr[i][1]=hr[i+1][1]*hr[i][1]%P;
for(int i=1;i<=m;i++) hc[i][0]=hc[i-1][0]*hc[i][0]%P;
hc[m][1]=power(hc[m][0],P-2);
for(int i=m-1;~i;i--) hc[i][1]=hc[i+1][1]*hc[i][1]%P;
for(int i=0;i<=n;i++) n1[0][i]=s1[0][i]=1;
for(int i=1;i<=m;i++){
for(int j=0;j<tagn[i][0];j++) n1[i][j]=0;
for(int j=tagn[i][0];j<=tagn[i][1];j++) n1[i][j]=fadd(n1[i][j-1],n1[i-1][j]);
for(int j=tagn[i][1]+1;j<=n;j++) n1[i][j]=n1[i][j-1];
for(int j=0;j<tags[i][0];j++) s1[i][j]=0;
for(int j=tags[i][0];j<=tags[i][1];j++) s1[i][j]=fadd(s1[i][j-1],s1[i-1][j]);
for(int j=tags[i][1]+1;j<=n;j++) s1[i][j]=s1[i][j-1];
}
for(int i=0;i<=n;i++) n2[m+1][i]=s2[m+1][i]=1;
for(int i=m;i;i--){
for(int j=0;j<tagn[i][0];j++) n2[i][j]=0;
for(int j=tagn[i][0];j<=tagn[i][1];j++) n2[i][j]=fadd(n2[i][j-1],n2[i+1][j]);
for(int j=tagn[i][1]+1;j<=n;j++) n2[i][j]=n2[i][j-1];
for(int j=0;j<tags[i][0];j++) s2[i][j]=0;
for(int j=tags[i][0];j<=tags[i][1];j++) s2[i][j]=fadd(s2[i][j-1],s2[i+1][j]);
for(int j=tags[i][1]+1;j<=n;j++) s2[i][j]=s2[i][j-1];
}
for(int i=0;i<=m;i++) w1[0][i]=e1[0][i]=1;
for(int i=1;i<=n;i++){
for(int j=0;j<tagw[i][0];j++) w1[i][j]=0;
for(int j=tagw[i][0];j<=tagw[i][1];j++) w1[i][j]=fadd(w1[i][j-1],w1[i-1][j]);
for(int j=tagw[i][1]+1;j<=m;j++) w1[i][j]=w1[i][j-1];
for(int j=0;j<tage[i][0];j++) e1[i][j]=0;
for(int j=tage[i][0];j<=tage[i][1];j++) e1[i][j]=fadd(e1[i][j-1],e1[i-1][j]);
for(int j=tage[i][1]+1;j<=m;j++) e1[i][j]=e1[i][j-1];
}
for(int i=0;i<=m;i++) w2[n+1][i]=e2[n+1][i]=1;
for(int i=n;i;i--){
for(int j=0;j<tagw[i][0];j++) w2[i][j]=0;
for(int j=tagw[i][0];j<=tagw[i][1];j++) w2[i][j]=fadd(w2[i][j-1],w2[i+1][j]);
for(int j=tagw[i][1]+1;j<=m;j++) w2[i][j]=w2[i][j-1];
for(int j=0;j<tage[i][0];j++) e2[i][j]=0;
for(int j=tage[i][0];j<=tage[i][1];j++) e2[i][j]=fadd(e2[i][j-1],e2[i+1][j]);
for(int j=tage[i][1]+1;j<=m;j++) e2[i][j]=e2[i][j-1];
}
i64 ans=0;
for(int i=0;i<=n;i++){
if(!i) n3[i]=n2[1][0],s3[i]=s2[1][0];
else{
n3[i]=s3[i]=0;
for(int j=1;j<=m;j++) if(tagn[j][0]<=i&&i<=tagn[j][1])
(n3[i]+=n1[j-1][i-1]*n2[j+1][i])%=P;
for(int j=1;j<=m;j++) if(tags[j][0]<=i&&i<=tags[j][1])
(s3[i]+=s1[j-1][i-1]*s2[j+1][i])%=P;
}
s3[i]=(s3[i-1]+s3[i]*hr[n-i][0])%P;
}
int lst=(tag2[n]?n:n+1);
for(int i=n-1;~i;i--){
(ans+=n3[i]*hr[i][1]%P*(s3[n-i-1]+P-(lst==n+1?0:s3[n-lst])))%=P;
if(tag2[i]) lst=i;
}
for(int i=0;i<=m;i++){
if(!i) w3[i]=w2[1][0],e3[i]=e2[1][0];
else{
w3[i]=e3[i]=0;
for(int j=1;j<=n;j++) if(tagw[j][0]<=i&&i<=tagw[j][1])
(w3[i]+=w1[j-1][i-1]*w2[j+1][i])%=P;
for(int j=1;j<=n;j++) if(tage[j][0]<=i&&i<=tage[j][1])
(e3[i]+=e1[j-1][i-1]*e2[j+1][i])%=P;
}
e3[i]=(e3[i-1]+e3[i]*hc[m-i][0])%P;
}
lst=(tag1[m]?m:m+1);
for(int i=m-1;~i;i--){
(ans+=w3[i]*hc[i][1]%P*(e3[m-i-1]+P-(lst==m+1?0:e3[m-lst])))%=P;
if(tag1[i]) lst=i;
}
for(int x=1;x<n;x++){
i64 sum=0;
for(int i=m;i;i--){
if(tagn[i][0]<=n-x&&n-x<=tagn[i][1]) (ans+=sum*n1[i-1][n-x]%P*n2[i+1][n-x-1])%=P;
if(tags[i][0]<=x&&x<=tags[i][1]) (sum+=s1[i-1][x-1]*s2[i+1][x])%=P;
}
sum=0;
for(int i=1;i<=m;i++){
if(tagn[i][0]<=n-x&&n-x<=tagn[i][1]) (ans+=sum*n1[i-1][n-x-1]%P*n2[i+1][n-x])%=P;
if(tags[i][0]<=x&&x<=tags[i][1]) (sum+=s1[i-1][x]*s2[i+1][x-1])%=P;
}
}
for(int x=1;x<m;x++){
i64 sum=0;
for(int i=1;i<n;i++){
if(tagw[i+1][0]<=m-x&&m-x<=tagw[i+1][1]) (ans+=sum*w1[i][m-x-1]%P*w2[i+2][m-x])%=P;
if(tage[i][0]<=x&&x<=tage[i][1]) (sum+=e1[i-1][x]*e2[i+1][x-1])%=P;
}
sum=0;
for(int i=n;i>1;i--){
if(tagw[i-1][0]<=m-x&&m-x<=tagw[i-1][1]) (ans+=sum*w1[i-2][m-x]%P*w2[i][m-x-1])%=P;
if(tage[i][0]<=x&&x<=tage[i][1]) (sum+=e1[i-1][x-1]*e2[i+1][x])%=P;
}
}
cout<<ans<<"\n";
}
int main(){
ios::sync_with_stdio(false),cin.tie(0);cout.tie(0);
cin>>T;
while(T--) solve();
return 0;
}