分析：
实质上很水的状压DP题。。。。。
因为m≤12m≤12，可以枚举哪些行被消除了，在状压转移删除的列
首先枚举一个maskmask表示要删除哪些行
设dp[i][j]dp[i][j]表示前i列已经被消除的行的状态为j，其中jj为 的子集
对于当前这一列，如果每一个有位置的行都被j覆盖了，那么就只能直接转移
如果存在一个位置，其没被mask覆盖，那么则必须在这一列选一个：存在于mask中但不存在于j中的点删除掉。
加几个卡常优化也是可以的。。。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define SF scanf
#define PF printf
#define MAXN 22
#define MAXM 4096+100
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
bool mp[MAXN][MAXN];
ll mod=100000000;
struct node{ll lar,mid,sma;node operator =(int a){sma=a;mid=0;lar=0;}node operator +=(const node &a) {sma=sma+a.sma;mid=sma/mod+mid+a.mid;lar=mid/mod+lar+a.lar;sma%=mod;mid%=mod;lar%=mod;}node operator *(const node &a){ll x=sma*a.sma;ll y=mid*a.sma+sma*a.mid;ll z=sma*a.lar+mid*a.mid+lar*a.sma;y+=x/mod;z+=y/mod;node res;res.sma=x%mod;res.mid=y%mod;res.lar=z%mod;return res;}bool operator ==(const node &a){if(sma!=a.sma)return 0;if(mid!=a.mid)return 0;return lar==a.lar; }void print(){if(lar!=0){PF("%I64d",lar);PF("%08I64d",mid);PF("%08I64d",sma);}else if(mid!=0){PF("%I64d",mid);PF("%08I64d",sma);}else{PF("%I64d",sma);}}
}dp[MAXN][MAXM],fac[MAXN],ans[MAXN],zero;
int n,m;
node solve(int x,int k1){dp[0][0]=1;for(int i=0;i<m;i++){bool flagx=0;for(int j=x;;j=((j-1)&x)){dp[i+1][j]=0;if(j==0)break;}for(int j=x;;j=((j-1)&x)){if(dp[i][j].sma==0&&dp[i][j].mid==0&&dp[i][j].lar==0){if(j==0)break;continue;}flagx=1;bool flag=0;int now=0;for(int k=0;k<n;k++)if(mp[k][i]==1){now|=(1<<k);if((x&(1<<k))==0)flag=1;}if(flag==0&&(now|x)==x)dp[i+1][j]+=dp[i][j];for(int k=0;k<n;k++)if((j&(1<<k))==0&&(x&(1<<k))!=0&&mp[k][i]==1)dp[i+1][j|(1<<k)]+=dp[i][j];if(j==0)break;}if(flagx==0)return zero;}return dp[m][x]*fac[k1];
}
bool check(int x,int k1){int res=0;for(int i=0;i<n;i++)for(int j=0;j<m;j++)if(((1<<i)&x)==0&&mp[i][j]==1)res|=(1<<j);return __builtin_popcount(res)<=k1;
}
char s[MAXN];
int main(){//freopen("k.in","r",stdin);//freopen("wa.out","w",stdout);int t,k;SF("%d",&t);fac[0]=1;for(int i=1;i<=12;i++){node i1;i1=i;fac[i]=fac[i-1]*i1;}while(t--){SF("%d%d%d",&n,&m,&k);for(int i=1;i<=k;i++)ans[i].lar=ans[i].mid=ans[i].sma=0;int ald=0;for(int i=0;i<n;i++){SF("%s",s);for(int j=0;j<m;j++){mp[i][j]=(s[j]=='Q');if(mp[i][j]==1)ald|=(1<<i);}}node las;las=0;for(int i=0;i<(1<<n);i++){int k1=__builtin_popcount(i);if(k1>k||(i|ald)!=ald||check(i,k1)==0)continue;node res=solve(i,k1);if((las==zero)==0&&(res==zero)==1)break;ans[k1]+=res; }for(int i=1;i<=k;i++){ans[i].print();PF("\n");}}
}