#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2010, M = 1000010;

int key[N][N];
void decrypt()
{
    for(int x = 1; x < N; x++)
        key[48 + x / 50][48 + x % 50] = key[48 + x / 50][48 + x % 50] ? key[48 + x / 50][48 + x % 50] : x;
}

int n, m, q;
int to[N][N];   // 操作
int p[N]; // 并查集缩点
vector<pair<int,int>> e;     // 存边
vector<int> edges[N];
bitset<N> f[N];
bool vis[N];
struct query    // 对询问离线
{
    int s, t, c, id;
    bool operator<(const query&Q)const
    {
        return c < Q.c;
    }
}que[M];

void read1(int i)
{
    string s;
    cin >> s;
    for(int j = 0; j < n * 2; j += 2)
        to[i][j / 2 + 1] = key[s[j]][s[j + 1]];
}
void read2(int i)
{
    string s;
    cin >> s;
    que[i].s = key[s[0]][s[1]];
    que[i].t = key[s[2]][s[3]];
    que[i].c = key[s[4]][s[5]];
    que[i].id = i;
}

int find(int x)
{
    if(x != p[x]) p[x] = find(p[x]);
    return p[x];
}

bitset<N> dp(int u)
{
    if(vis[u]) return f[u];
    vis[u] = true;
    f[u].reset();
    f[u][u] = 1;

    for(auto v: edges[u])
    {
        v = find(v);
        if(u == v) continue;
        f[u] |= dp(v);
    }
    return f[u];
}

void topsort()  // 再缩点
{
    vector<int> d(n + 1, 0), st(n + 1, 0);
    for(int i = 1; i <= n; i++)
        if(i == p[i])
            for(auto u: edges[i])
            {
                u = find(u);
                if(u != i) d[u] ++;
            }

    queue<int> q;
    for(int i = 1; i <= n; i++)
        if(i == p[i] && d[i] == 0)
            q.push(i);
    while(q.size())
    {
        int u = q.front();
        st[u] = 1;
        q.pop();
        for(auto v: edges[u])
        {
            v = find(v);
            if(!(--d[v])) q.push(v);
        }
    }

    for(int u = 1; u <= n; u++)
        for(auto v: edges[u])
        {
            u = find(u), v = find(v);
            if(!st[u] && !st[v] && u != v)
                p[v] = u;
        }
}

void build()    // 重新建图
{
    for(int i = 1; i <= n; i++)
    {
        vis[i] = false;
        edges[i].clear();
    }
    for(auto [u, v]: e)
    {
        u = find(u), v = find(v);
        if(u != v) edges[u].push_back(v);
    }
    topsort();
    for(int i = 1; i <= n; i++)
    {
        vis[i] = false;
        edges[i].clear();
    }
    for(auto [u, v]: e)
    {
        u = find(u), v = find(v);
        if(u != v) edges[u].push_back(v);
    }
    for(int i = 1; i <= n; i++)
        if(i == p[i])
            dp(i);
}

void modify(int k)  // 处理第 k 种操作
{
    vector<vector<int>> from(n + 1);
    for(int i = 1; i <= n; i++)
        from[to[k][i]].push_back(i);

    int flag = 0, empy = 0;
    for(int i = 1; i <= n; i++)
        if(from[i].size() > 2)
            return;
        else if(from[i].size() == 2)
        {
            if(flag) return;
            flag = i;
        }
        else if(from[i].size() == 0)
            empy = i;

    if(flag) // 两条边
    {
        for(auto u: from[flag])
            e.push_back({u, empy});
    }
    else // 若干个环
    {
        for(int i = 1; i <= n; i++)
        {
            int u = find(i), v = find(to[k][i]);
            if(u != v) p[u] = v;
        }
    }

    build();
}

void solve()
{
    cin >> n >> m >> q;
    for(int i = 1; i <= m; i++)
        read1(i);
    for(int i = 1; i <= q; i++)
        read2(i);

    e.clear();
    for(int i = 1; i <= n; i++)
    {
        f[i].reset();
        f[i][i] = 1;
    }
    for(int i = 1; i <= n; i++)
        p[i] = i;
    sort(que + 1, que + q + 1);
    vector<int> ans(q + 1);
    for(int i = 1, j = 1; i <= q; i++)
    {
        int s = que[i].s, t = que[i].t, c = que[i].c, id = que[i].id;
        while(j <= c) modify(j ++);
        s = find(s), t = find(t);
        ans[id] = f[s][t];
    }
    for(int i = 1; i <= q; i++)
        cout << ans[i];
    cout << '\n';
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    decrypt();
    
    int T = 1;
    cin >> T;
    while(T --)
        solve();
    
    return 0;
}

/*
2
5 2 4
0305040201
0404040404
030300
020500
050102
020501
6 2 4
030603010601
010203060504
030202
060402
050602
060401

1011
0100
==========
1
3 3 6
020202
030301
030201
020102
030203
010201
010303
020303
010202

010101
*/