#include<stdio.h>#include<queue>#include<string.h>#include<iostream>#define inf 0x3f3f3f3f#define M 2080#define N 10080using namespace std;int sumflow;struct Edge{ int u,v,cap,cost,ednxt;}edge[M*1000];int edn,head[M],dist[M],pp[M];bool vis[M];int init(){ edn=0;memset(head,-1,sizeof(head));}void add(int u,int v,int cap,int cost){ edge[edn].u=u;edge[edn].v=v;edge[edn].cap=cap;edge[edn].cost=cost,edge[edn].ednxt=head[u];head[u]=edn++; edge[edn].u=v;edge[edn].v=u;edge[edn].cap=0; edge[edn].cost=-cost, edge[edn].ednxt=head[v];head[v]=edn++;}bool spfa(int s,int t,int n){ int i,u,v; queue<int> qu; memset(vis,0,sizeof(vis)); memset(pp,-1,sizeof(pp)); for(i=0;i<=n;i++) dist[i]=inf; vis[s]=1;dist[s]=0; qu.push(s); while(!qu.empty()) { u=qu.front();qu.pop();vis[u]=0; for(i=head[u];i!=-1;i=edge[i].ednxt) { v=edge[i].v; if(edge[i].cap&&dist[v]>dist[u]+edge[i].cost) { dist[v]=dist[u]+edge[i].cost; pp[v]=i; if(!vis[v]) { vis[v]=1; qu.push(v); } } } } if(dist[t]==inf) return false; return true;}int mcmf(int s,int t,int n){ int flow=0; int i,minflow,mincost; mincost=0; while(spfa(s,t,n)) { minflow=inf+1; for(i=pp[t];i!=-1;i=pp[edge[i].u]) { if(edge[i].cap<minflow) { minflow=edge[i].cap; } } flow+=minflow; for(i=pp[t];i!=-1;i=pp[edge[i].u]) { edge[i].cap-=minflow; edge[i^1].cap+=minflow; } mincost+=dist[t]*minflow; } sumflow=flow; return mincost;}int str1[N];int str2[N];int mapstr[30][30];double f(int m){ init(); memset(mapstr,0,sizeof(mapstr)); for(int i=0;i<m;i++){ int t1=str1[i]; int t2=str2[i]; mapstr[t1][t2]++; } int s=0;int t=53; for(int i=1;i<=26;i++){ add(s,i,1,0); add(i+26,t,1,0); } for(int i=1;i<=26;i++){ for(int j=1;j<=26;j++){ if(mapstr[i][j]){ add(i,j+26,1,-mapstr[i][j]); } } } int ans=-mcmf(s,t,t+1); double ans1=(ans*1.0)/m; return ans1;}int main(){ int cas;while(~scanf("%d",&cas)){ while(cas--){ int m,k1,n;scanf("%d%d%d",&m,&k1,&n); int t1; char tmp[10]; for(int i=0;i<m;i++) scanf("%s",tmp),str1[i]=tmp[0]-'A'+1; for(int i=0;i<n;i++){ for(int j=0;j<m;j++) scanf("%s",tmp),str2[j]=tmp[0]-'A'+1; double ans=f(m); printf("%.4lfn",ans); } } } return 0;}
