#include<bits/stdc++.h>
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef long long ll;
typedef pair<ll,ll>pll;
const ll INF=0x3f3f3f3f;
const ll MO9=998244353;
const ll MO1=1e9+7;
const ll MO=MO9;
const int N=5e5+5;
ll n,m;
struct node{
    int type;
    int ne[2005];
    vector<int>vec;
    int c;
}c[2005];

int t[2005];
int deg[2005];
void read(){
    for(int i=1;i<=m;i++){
        string s;
        cin>>s;
        for(int j=1;j<=n;j++){
            deg[j]=0;
            int i1=2*(j-1);
            int i2=i1+1;
            t[j]=(s[i1]-48)*50+s[i2]-48;
        }
        int ma=0;
        for(int j=1;j<=n;j++){
            deg[t[j]]++;
            ma=max(deg[t[j]],ma);
        }
        if(ma==1){
            for(int j=1;j<=n;j++){
                c[i].ne[j]=t[j];
            }
            c[i].type=1;
        }
        else if(ma==2){
            int cnt=0;
            c[i].vec.clear();
            c[i].type=2;
            for(int j=1;j<=n;j++){
                if(deg[t[j]]==2){
                    cnt++;
                    c[i].vec.push_back(j);
                }
                if(deg[j]==0){
                    c[i].c=j;
                }
                if(cnt>2){
                    c[i].type=0;
                    break;
                }
            }
        }
        else{
            c[i].type=0;
        }
    }
}

int fa[N];
int find(int x){
    if(fa[x]!=x)fa[x]=find(fa[x]);
    return fa[x];
}
vector<pair<int,int> >G[2005];
int dis[2005][2005];
int vis[2005];
void init(){
    for(int i=1;i<=n;i++){
        fa[i]=i;
        G[i].clear();
    }
    for(int i=1;i<=m;i++){
        if(c[i].type==0)continue;
        else if(c[i].type==1){
            for(int j=1;j<=n;j++){
                int pa=find(j),pb=find(c[i].ne[j]);
                if(pa==pb)continue;
                G[pa].push_back({pb,i});
                G[pb].push_back({pa,i});
                fa[pa]=pb;
            }
        }
        else if(c[i].type==2){
            int pa=find(c[i].vec[0]),pb=find(c[i].vec[1]);
            int pc=find(c[i].c);
            if(pa!=pc){
                G[pa].push_back({pc,i});
            }
            if(pb!=pc){
                G[pb].push_back({pc,i});
            }
        }
    }
    for(int s=1;s<=n;s++){
        for(int i=0;i<=n;i++)vis[i]=0;
        for(int i=1;i<=n;i++)dis[s][i]=INF;
        dis[s][s]=0;
        priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >pq;
        pq.push({0,s});
        while(!pq.empty()){
            auto t=pq.top();
            pq.pop();
            int W=t.first;
            int u=t.second;
            if(vis[u])continue;
            vis[u]=1;
            dis[s][u]=W;
            for(auto [v,w]:G[u]){
                if(vis[v])continue;
                pq.push({max(W,w),v});
            }
        }
    }
}
void solve(){
    int q;
    cin>>n>>m>>q;
    read();

    init();

    for(int i=1;i<=q;i++){
        string s;
        cin>>s;
        int a,b,c;
        a=(s[0]-48)*50+s[1]-48;
        b=(s[2]-48)*50+s[3]-48;
        c=(s[4]-48)*50+s[5]-48;
        cout<<(dis[a][b]<=c);
    }
    cout<<'\n';
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int ttt=1;
    cin>>ttt;
    while(ttt--)
    solve();
    return 0;
}