观察到 $n$ 很小，大致猜测为状压类做法。显然可以将两种品种的牛分开来考虑，询问的答案即为两种牛分别的答案之积。

考虑如何求出若干头牛分配礼物的方案数 $f_S$，其中 $S$ 为压缩后的状态。我们发现分配礼物的过程可以构成若干个环，不妨令 $g_S$ 表示状态 $S$ 中的所有牛构成一个环的方案数（一头牛也视为一种特殊的“环”）。于是 $f_S=\sum_{T \subseteq S} f_{S \setminus T} \times g_T$（为了防止算重，我们钦定 $T$ 包含 $S$ 中编号最小的一头牛），重点来到如何计算 $g$。

我们考虑 $S$ 构成一个环的方案数，考虑断环为链，发现环上任意一点均可视为起点，类似上面的可以钦定 $S$ 中编号最小的一头牛为起点，令 $h_{S,i}$ 表示 $S$ 中以编号最小的牛为起点、$i$ 为终点的链的方案数，转移是简单的：$h_{S,i} \rightarrow h_{S \cup j,j}$（存在 $i$ 到 $j$ 的边），这部分的处理是 $\mathcal{O}(2^nn^2)$ 的。有了 $h$ 就可以比较方便的计算 $g$：$g_S=\sum h_{S,i}$，记得考虑链的首尾是否能相连。

以上，总的时间复杂度为 $\mathcal{O}(2^nn^2+3^n+Qn)$。

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

using ll=long long;
const int N=20,Pw=1<<18|2;
int n,q,p[N][N],rnk[N][N];
ll h[Pw][N],g[Pw],f[Pw];
char species[N];

int main() {
	scanf("%d",&n);
	for(int i=1;i<=n;i++) {
		for(int j=1;j<=n;j++) scanf("%d",&p[i][j]),rnk[i][p[i][j]]=j;
		h[1<<i-1][i]=1;
	}
	auto check=[&](int u,int v)->bool {return rnk[v][u]<=rnk[v][v];};
	for(int stat=1;stat<(1<<n);stat++) {
		int beginn=__builtin_ctz(stat)+1;
		for(int i=1;i<=n;i++) {
			if(!((stat>>i-1)&1)||!h[stat][i]) continue ;
			for(int j=beginn+1;j<=n;j++) {
				if(((stat>>j-1)&1)||!check(i,j)) continue ;
				h[stat|(1<<j-1)][j]+=h[stat][i];
			}
		}
	}
	for(int stat=1;stat<(1<<n);stat++) {
		int beginn=__builtin_ctz(stat)+1;
		for(int i=1;i<=n;i++) {
			if(!((stat>>i-1)&1)||!check(i,beginn)) continue ;
			g[stat]+=h[stat][i];
		}
	}
	f[0]=1;
	for(int stat=1;stat<(1<<n);stat++) {
		int prev=stat,thre=1<<__builtin_ctz(stat);
		while(prev) {
			if(prev&thre) f[stat]+=f[stat^prev]*g[prev];
			prev=(prev-1)&stat;
		}
	}
	for(scanf("%d",&q);q--;) {
		scanf("%s",species); int stat=0;
		for(int i=0;i<n;i++) if(species[i]=='H') stat|=(1<<i);
		printf("%lld\n",f[stat]*f[((1<<n)-1)&(~stat)]);
	}
	return 0;
}