#include<bits/stdc++.h>
using namespace std;
const int N=2010,M=1e6+10;
int T,n,L,Q;
int t[N][N],r[N][N];
bool ans[M];
struct node{
	int id,a,b,c;
}q[M];
vector<int> Eu,Ev;
vector<int> sd[N];
vector<int> G[N];
bool cmp(node x,node y){
	return x.c<y.c;
}

int turn_ch(char x,char y){
	return (x-48)*50+y-48;
}
void readin(){
	Eu.clear();
	Ev.clear();
	
	
	static char ch[N*2];
	for(int i=1;i<=L;i++){
		scanf("%s",ch);
		for(int j=1;j<=n;j++){
			r[i][j]=0;
		}
		for(int j=1;j<=n;j++){
			t[i][j]=turn_ch(ch[2*j-2],ch[2*j-1]);
			r[i][t[i][j]]=j;
		}
	}
	for(int i=1;i<=Q;i++){
		scanf("%s",ch);
		q[i].id=i;
		q[i].a=turn_ch(ch[0],ch[1]);
		q[i].b=turn_ch(ch[2],ch[3]);
		q[i].c=turn_ch(ch[4],ch[5]);
	}
}

int fa[N];
int find(int x){
	return fa[x]==x?x:fa[x]=find(fa[x]);
}
void merge(int x,int y){
	int fx=find(x),fy=find(y);
	if(fx!=fy)fa[fx]=fy;
}


void add(int u,int v){
	G[u].push_back(v);
}
void rebuild(){
	for(int i=1;i<=n;i++){
		sd[i].clear();
		G[i].clear();
	}
	for(int i=1;i<=n;i++){
		sd[find(i)].push_back(i);
	}
	
	for(int i=1;i<=n;i++){
		if(sd[i].size()<2)continue;
		for(int j=1;j<sd[i].size();j++){
			add(sd[i][j-1],sd[i][j]);
		}
		add(sd[i][sd[i].size()-1],sd[i][0]);
	}
	for(int i=0;i<Eu.size();i++){
		add(Eu[i],Ev[i]);
	}
}

int low[N],dfn[N],clk,B,bl[N];
void init(){
	B=clk=0;
	memset(dfn,0,sizeof(dfn));
}
void tarjan(int u){
	static int st[N],p;
	static bool in[N];
	dfn[u]=low[u]=++clk;
	st[p++]=u;in[u]=true;
	for(int &v:G[u]){
		if(!dfn[v]){
			tarjan(v);
			low[u]=min(low[u],low[v]);
		}else if(in[v])low[u]=min(low[u],dfn[v]);
	}
	if(dfn[u]==low[u]){
		while(1){
			int x=st[--p];in[x]=false;
			bl[x]=B; 
			if(x==u)break;
		}
		++B;
	}
}

vector<int> E[N];
int deg[N];
int xu[N],cnt;
void tuopu(){
	queue<int> q;
	for(int u=0;u<B;u++){
		deg[u]=0;
	}
	for(int u=0;u<B;u++){
		for(int i=0;i<E[u].size();i++){
			int v=E[u][i];
			deg[v]++;
		}
	}
	
	cnt=0;
	for(int u=0;u<B;u++){
		if(deg[u]==0){
			xu[cnt++]=u;
			q.push(u);
		}
	}
	
	while(!q.empty()){
		int u=q.front();q.pop();
		for(int i=0;i<E[u].size();i++){
			int v=E[u][i];
			deg[v]--;
			if(deg[v]==0){
				xu[cnt++]=v;
				q.push(v);
			}
		}
	}
}

bitset<N> b[N];

void dp(){
//	printf("cnt=%d\n",cnt);
	for(int i=0;i<B;i++){
		b[i].reset();
	}
	assert(cnt==B);
	for(int i=cnt-1;i>=0;i--){
		int u=xu[i];
		b[u][u]=1;
		for(int j=0;j<E[u].size();j++){
			int v=E[u][j];
			b[u]|=b[v];
		}
	}
}

bool check(int x,int y){
//	printf("x=%d y=%d\n",x,y); 
	return b[x][y];
}

// update t[p]
bool update(int p){
	static int cnt[N];
	for(int j=1;j<=n;j++){
		cnt[j]=0;
	}
	for(int j=1;j<=n;j++){
		cnt[t[p][j]]++;
	}
	
	int q=0;
	for(int j=1;j<=n;j++){
		if(cnt[j]>=3)return false;
		if(cnt[j]==2){
			if(q)return false;
			q=j;
		}
	}
	
	if(q){
		int c1=0,c2=0,d=q;
		for(int j=1;j<=n;j++){
			if(t[p][j]==q){
				if(c1)c2=j;
				else c1=j;
			}
		}
		
		bool b1=false,b2=false;
		if(d==c1)b1=true;
		if(d==c2)b2=true;
		while(t[p][d]!=q){
			d=t[p][d];
			if(d==c1)b1=true;
			if(d==c2)b2=true;
		}
		
		if(b2){
			swap(b1,b2);
			swap(c1,c2);
		}
		
		while(r[p][c2]!=0)c2=r[p][c2];
		
		Eu.push_back(c1);
		Ev.push_back(c2);
		
	}else{
		for(int j=1;j<=n;j++){
			merge(j,t[p][j]);
		}
	}
	
	rebuild();
	
	init();
	for(int i=1;i<=n;i++){
		if(!dfn[i])tarjan(i);
	}
	
//	printf("B=%d\n",B);
	for(int i=0;i<B;i++){
		E[i].clear();
	}
	for(int i=1;i<=n;i++){
		for(int j=0;j<G[i].size();j++){
			int u=i,v=G[i][j];
			if(bl[u]!=bl[v])E[bl[u]].push_back(bl[v]);
		}
	}
	
	tuopu();
	dp();
	return true;
}

void work(){
	for(int i=1;i<=n;i++)fa[i]=i;
	sort(q+1,q+Q+1,cmp);
	
	bool flag=false;
	int now=0;
	for(int i=1;i<=Q;i++){
		while(now<q[i].c){
			now++;
			if(update(now))flag=true;
		}
		
		if(flag)ans[q[i].id]=check(bl[q[i].a],bl[q[i].b]);
		else ans[q[i].id]=(q[i].a==q[i].b);
	}
	
	for(int i=1;i<=Q;i++){
		if(ans[i])putchar('1');
		else putchar('0');
	}
	putchar('\n');
}
int main(){
	scanf("%d",&T);
	while(T--){
		scanf("%d%d%d",&n,&L,&Q);
		readin();
		work();
	}
}