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

const int maxn = 2010, maxd = 1 << 17 | 1;
int lbt[maxd];
void init(){
    //lbt[i]表示i的二进制表示中lowbit在右起第几位(0-index) 用于lowbit函数的初始化 
    lbt[0] = -1;
    for(int i = 1; i < maxd; ++i)
        lbt[i] = i & 1 ? 0 : lbt[i >> 1] + 1;
}
//lowbit(bitset,low,upp) 求该bitset的[low,upp]内的lowbit 
int lowBit(bitset<maxn> const &msk, size_t const &low, size_t const &upp) {
    typedef unsigned long long _WordT;
    _WordT *seq = (_WordT *)&msk;
    size_t pL = low >> 6, pR = upp >> 6;
    size_t qL = low & 63, qR = upp & 63;
    for(size_t i = pL; i <= pR; ++i) {
        _WordT val = seq[i];
        if(i == pR && qR < 63)
            val &= (static_cast<_WordT>(1) << (qR + 1)) - 1;
        if(i == pL)
            val = (val >> qL) << qL;
        if(val != static_cast<_WordT>(0)) {
            size_t ret = i << 6;
            if((val & ((static_cast<_WordT>(1) << 32) - 1)) == static_cast<_WordT>(0)) {
                val >>= 32;
                ret |= 32;
            }
            if((val & ((static_cast<_WordT>(1) << 16) - 1)) == static_cast<_WordT>(0)) {
                val >>= 16;
                ret |= 16;
            }
            return ret + lbt[static_cast<int>(val & ((static_cast<_WordT>(1) << 16) - 1))];
        }
    }
    return -1;
}

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;     // 存边
bitset<N> f[N], edges[N], cur, nxt, tmp;
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];
}

void bfs(int u)
{
    f[u].reset();
    f[u].set(u);
    cur = f[u];
    nxt = cur | edges[u];

    for(int i = 0; i < n; i++)
    {
        tmp = nxt ^ cur;
        cur = f[u] = nxt;
        for(int v = lowBit(tmp, 1, n); v != -1; v = lowBit(tmp, v + 1, n))
            nxt |= edges[v] | f[v];
        if(cur == nxt) break;
    }
}

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

    for(int i = 1; i <= n; i++)
        if(i == p[i])
            bfs(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();
    init();
    
    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
*/