link
#4WA
C++14，O2
#include<bits/stdc++.h>
typedef long long ll;
//#define int long long
const int N=50;
const int gw[15]={0,1,9,10,18,19,27,28,29,30,31,32,33,34};
using namespace std;
int t,a[N],tot,c[N][N];
ll f[N][5][5][5][5],cnt[N];
bool b[N];
signed main(){
register int i,j,k,l,u;
c[0][0]=1;
for(i=1;i<=4;i++){
c[i][0]=1;
for(j=1;j<=i;j++)
c[i][j]=c[i-1][j]+c[i-1][j-1];
}
scanf("%d",&t);
while(t--){
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
memset(f,0,sizeof(f));
memset(cnt,0,sizeof(cnt));
while(1){
string x;
cin>>x;
if(x[0]=='0')break;
else if(x[0]=='E')a[28]++;
else if(x[0]=='S')a[29]++;
else if(x[0]=='W')a[30]++;
else if(x[0]=='N')a[31]++;
else if(x[0]=='Z')a[32]++;
else if(x[0]=='F')a[33]++;
else if(x[0]=='B')a[34]++;
else if(x[1]=='m')a[x[0]-'0']++;
else if(x[1]=='p')a[x[0]+9-'0']++;
else if(x[1]=='s')a[x[0]+18-'0']++;
}
// for(int i=1;i<=34;i++)
// printf("a[%d]=%d\n",i,a[i]);
while(1){
string x;
cin>>x;
if(x[0]=='0')break;
else if(x[0]=='E')b[28]=1;
else if(x[0]=='S')b[29]=1;
else if(x[0]=='W')b[30]=1;
else if(x[0]=='N')b[31]=1;
else if(x[0]=='Z')b[32]=1;
else if(x[0]=='F')b[33]=1;
else if(x[0]=='B')b[34]=1;
else if(x[1]=='m')b[x[0]-'0']=1;
else if(x[1]=='p')b[x[0]+9-'0']=1;
else if(x[1]=='s')b[x[0]+18-'0']=1;
}
// for(int i=1;i<=34;i++)
// printf("b[%d]=%d\n",i,b[i]);
for(i=1;i<=34;i++)a[i]=4-a[i];
ll ans=0;
for(i=1;i<=13;i++){
ll t=1;
for(int j=1;j<=13;j++){
if(i==j){
if(a[gw[j]]<2)t=0;
else t*=c[a[gw[j]]][2]*(b[gw[j]]?4:1);
}
else{
if(a[gw[j]]<1)t=0;
else t*=c[a[gw[j]]][1]*(b[gw[j]]?2:1);
}
}
ans=max(ans,t*13);
}
tot=0;
for(i=1;i<=34;i++){
if(a[i]>=2)cnt[++tot]=c[a[i]][2]*(b[i]?4:1);
}
if(tot>=7){
sort(cnt+1,cnt+1+tot);
ll t=1;
for(i=tot;i>tot-7;i--)t*=cnt[i];
ans=max(ans,t*7);
}
f[0][0][0][0][0]=1;
for(i=0;i<34;i++){
for(j=0;j<=4;j++){
for(k=0;k<3&&j+k<=4;k++){
if(k>=1&&(i==9||i==18||i>=27))break;
for(l=0;l<3&&j+k+l<=4;l++){
if(l>=1&&(i==9||i==18||i>=27))break;
if(!f[i][j][k][l][0]&&!f[i][j][k][l][1])continue;
for(u=k+l;u<=a[i+1];u++){
ll t=c[a[i+1]][u]*(b[i+1]?(1<<u):1);
if(j+u<=4&&u-k-l<3){
f[i+1][j+k][l][u-k-l][0]=max(f[i+1][j+k][l][u-k-l][0],f[i][j][k][l][0]*t);
f[i+1][j+k][l][u-k-l][1]=max(f[i+1][j+k][l][u-k-l][1],f[i][j][k][l][1]*t);
}
if(u-k-l-2>=0&&j+u-2<=4)
f[i+1][j+k][l][u-k-l-2][1]=max(f[i+1][j+k][l][u-k-l-2][1],f[i][j][k][l][0]*t);
if(u-k-l-3>=0&&j+u-2<=4){
f[i+1][j+k+1][l][u-k-l-3][0]=max(f[i+1][j+k][l][u-k-l-3][0],f[i][j][k][l][0]*t);
f[i+1][j+k+1][l][u-k-l-3][1]=max(f[i+1][j+k][l][u-k-l-3][1],f[i][j][k][l][1]*t);
}
if(u==4&&!k&&!l&&j<=3){
f[i+1][j+1][0][0][0]=max(f[i+1][j+1][0][0][0],f[i][j][k][l][0]*t);
f[i+1][j+1][0][0][1]=max(f[i+1][j+1][0][0][1],f[i][j][k][l][1]*t);
}
}
}
}
}
}
ans=max(ans,f[34][4][0][0][1]);
cout<<ans<<'\n';
}
return 0;
}