using namespace std;
# include<bits/stdc++.h>
namespace zhu{
# define mem(a,b) memset(a,b,sizeof a)
# define mec(a,b) memcpy(a,b,sizeof a)
using ll=long long;
using db=double;
using ull=unsigned long long;
using uint=unsigned int;
# define mkp make_pair
using pii= pair<int,int>;
# define TEM template<typename T>
TEM void ckm(T &x,T y){
	if(y<x) x=y;
}
TEM void ckx(T &x,T y){
	if(y>x) x=y;
}
# define endl '\n'
int N,M,Q;
constexpr int maxn=2000+5,mod=998244353;
int qp(int x,int y){
	int ret=1;
	while(y){
		if(y&1) ret=1ll*ret*x%mod;
		x=1ll*x*x%mod;
		y>>=1;
	}
	return ret;
}
int ny(int x){return qp(x,mod-2);}
string edge[maxn];
string qry;
struct aqua{
	int a,b,id;
};
vector<aqua>xunwen[maxn];bool ans[1000100];
vector<int>ed[maxn];
int bel[maxn],zhiz=0,dfn[maxn],low[maxn],tmp=0;
int sta[maxn],top=0;
bool vis[maxn];
int f[maxn];int find(int x){return f[x]==x?x:f[x]=find(f[x]);}
bitset<maxn>to[maxn]; 
void work(int x,string &s){
	int a=(s[0]-48)*50+(s[1]-48);
	int b=(s[2]-48)*50+(s[3]-48);
	int c=(s[4]-48)*50+(s[5]-48);
//	cerr<<"Q "<<a<<' '<<b<<' '<<c<<endl;
	xunwen[c].push_back({a,b,x});
}
void work(string &s){
	// cerr<<"E ";
	static int _vis[maxn];
	for(int i=1;i<=N;i++) _vis[i]=0;
	bool fg=0;int A,B;
	for(int i=1;i<=N;i++){
		int aim=(s[i*2-2]-48)*50+(s[i*2-1]-48);
		// cerr<<i<<' '<<aim<<endl;
		if(!_vis[aim]) _vis[aim]=i;
		else if(fg) return;
		else{
			fg|=1;
			A=i,B=_vis[aim];
		}
	}
	if(!fg){
		for(int i=1;i<=N;i++){
			if(find(i)!=find(_vis[i])){
				int a=find(i),b=find(_vis[i]);
				if(ed[a].size()<ed[b].size()) swap(a,b); 
				for(auto x:ed[b]) ed[a].emplace_back(find(x));
				f[find(b)]=find(a);ed[b].clear();
			}
		}
	}
	else{
		for(int i=1;i<=N;i++){
			if(!_vis[i]){
//				cerr<<"!"<<A<<' '<<i<<endl;
				if(find(A)!=find(i))ed[find(A)].emplace_back(find(i));
				if(find(B)!=find(i))if(find(A)!=find(B))ed[find(B)].emplace_back(find(i));
				return;
			}
		}
	}
}
void tarjan(int rt){
	assert(rt==find(rt));
	dfn[rt]=low[rt]=++tmp;
	sta[++top]=rt;
	vis[rt]=1;
	for(auto x:ed[rt]){
		x=find(x); 
		if(!dfn[x]){
			tarjan(x);
			low[rt]=min(low[rt],low[x]);
		}else if(vis[x]) low[rt]=min(low[rt],low[x]);
	}
	if(low[rt]==dfn[rt]){
		zhiz++;
		while(sta[top+1]!=rt){
			bel[sta[top]]=zhiz;
			vis[sta[top]]=0;
			--top;
		}
	}
}
bool v[maxn];
vector<int>ve[maxn];
void dfs(int x){
	v[x]|=1;
	for(auto t:ve[x]){
		if(!v[t]) dfs(t);
		to[x]|=to[t];
	}
}
void solve(int x){
	work(edge[x]);
	for(int i=1;i<=N;i++) bel[i]=dfn[i]=low[i]=vis[i]=sta[i]=v[i]=0,ve[i].clear();
	zhiz=0;tmp=0;top=0;
	for(int i=1;i<=N;i++) if(find(i)==i) if(!dfn[i]) tarjan(i);
	for(int i=1;i<=zhiz;i++) to[i].reset();
	for(int i=1;i<=N;i++){
		if(i==find(i))
		for(auto x:ed[i]){
//			cerr<<"!!"<<x<<' '<<i<<endl;
			if(bel[i]!=bel[find(x)])ve[bel[i]].emplace_back(bel[find(x)]); 
		}
	}
	for(int i=1;i<= zhiz;i++){
		to[i][i]=1;
	}
	for(int i=1;i<=zhiz;i++){
		if(!v[i]) dfs(i);
	}
	for(auto p:xunwen[x]){
		int a=p.a,b=p.b,id=p.id;
		if(to[bel[find(a)]][bel[find(b)]]) ans[id]|=1;
		else ans[id]=0;
	}
}int T;
void solve(){
	cin>>N>>M>>Q;
	// if(T==398) cout<<N<<' '<<M<<' '<<Q<<' ';
	for(int i=1;i<=N;i++) f[i]=i;
	for(int i=1;i<=M;i++){
		cin>>edge[i];
		// if(T==398) cout<<edge[i]<<' '
;	}
	for(int i=1;i<=Q;i++) cin>>qry,work(i,qry);
	for(auto x:xunwen[0]){
		if(x.a==x.b) ans[x.id]|=1;
		else ans[x.id]=0;
	}
	for(int i=1;i<=M;i++){
		solve(i);
	}
	// if(T==399) return;
	for(int i=1;i<=Q;i++) cout<<int(ans[i]);
	cout<<'\n';
	for(int i=0;i<=M;i++){
		xunwen[i].clear();
	}
	for(int i=1;i<=N;i++) ed[i].clear();
}
int MAIN(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>T;
	while(T--)
	solve();
	return 0;
}
};
# undef int
using namespace zhu;
int main(){
	return MAIN();
}/*
2
5 5 0
0405020501
0404050302
0105050105
0304010205
0402030205
5 5 1
0203050204 
0102050403 
0304040305 
0201020104 
0302050202
010205

1->1 4->1
3 5


*/