#include <bits/stdc++.h>
#define sz(x) ((int)(x).size())
#define all(x) begin(x), end(x)
#ifdef memset0
#define log(...) fprintf(stderr, __VA_ARGS__)
#else
#define endl '\n'
#define log(...) (void(0))
#endif
using namespace std;
using ll = long long;
using lf = long double;
using ull = unsigned long long;

const int N = 2e3 + 9, Q = 1e6 + 9;
int T, n, m, q, ans[Q], deg[N];
bool vis[N];
vector<tuple<int, int, int>> qry[N];
bitset<N> bit[N];

struct Graph {
  int p[N];
  vector<vector<int>> cir;
  vector<pair<int, int>> ext;

  bool init() {
    // clear
    ext.clear();
    cir.clear();

    fill(deg + 1, deg + n + 1, 0);
    for (int i = 1; i <= n; i++) deg[p[i]]++;

    int cnt[5];
    fill(all(cnt), 0);
    for (int i = 1; i <= n; i++) {
      if (deg[i] >= 3) return false;
      cnt[deg[i]]++;
    }
    // log("! cnt={%d,%d,%d}\n", cnt[0], cnt[1], cnt[2]);
    if (cnt[0] == 1 && cnt[2] == 1) {
      int dg0 = -1, dg2 = -1;
      for (int i = 1; i <= n; i++)
        if (deg[i] == 0) {
          dg0 = i;
        }
      for (int i = 1; i <= n; i++)
        if (deg[i] == 2) {
          dg2 = i;
        }
      vector<int> link;
      for (int u = dg0; u != dg2; u = p[u]) {
        link.emplace_back(u);
      }
      for (int i = 1; i <= n; i++)
        if (p[i] == dg2) {
          ext.emplace_back(link.front(), i);
        }
      assert(ext.size() == 2 && cir.size() == 0);
    } else if (cnt[0] == 0 && cnt[2] == 0) {
      fill(vis + 1, vis + n + 1, false);
      for (int i = 1; i <= n; i++)
        if (!vis[i]) {
          cir.push_back({i});
          // log("extract circle from %d\n", i);
          vis[i] = true;
          for (int u = p[i]; u != i; u = p[u]) {
            vis[u] = true;
            cir.back().emplace_back(u);
          }
        }
    } else {
      return false;
    }
    return true;
  }
} t[N];

void read_buffer(int *s, int n) {
  string buffer;
  do {
    getline(cin, buffer);
  } while (sz(buffer) == 0);
  // log("! buffer_len=%d n=%d\n", sz(buffer), n);
  assert(sz(buffer) == (n << 1));
  for (int i = 0; i < n; i++) {
    int h = buffer[i << 1] - 48;
    int l = buffer[i << 1 | 1] - 48;
    s[i] = h * 50 + l;
  }
}

int uni[N];
int find(int x) {
  if (x == uni[x]) return x;
  return uni[x] = find(uni[x]);
}
void merge_all(const vector<int> &v) {
  for (int i = 1; i < sz(v); i++) uni[find(v[i])] = find(v[0]);
}

vector<int> G[N], stk, con[N];
int tim, cnt, dfn[N], low[N], ins[N], col[N];
void tarjan(int u) {
  dfn[u] = low[u] = ++tim;
  ins[u] = true;
  stk.push_back(u);
  for (int v : G[u]) {
    if (!dfn[v]) {
      tarjan(v);
      low[u] = min(low[u], low[v]);
    } else if (ins[v]) {
      low[u] = min(low[u], dfn[v]);
    }
  }
  if (dfn[u] == low[u]) {
    ++cnt;
    while (stk.back() != u) {
      col[stk.back()] = cnt;
      ins[stk.back()] = false;
      stk.pop_back();
    }
    col[stk.back()] = cnt;
    ins[stk.back()] = false;
    stk.pop_back();
  }
}

int main() {
#ifdef memset0
  freopen("L.in", "r", stdin);
#endif
  cin.tie(0)->sync_with_stdio(0);
  cin >> T;
  while (T--) {

    cin >> n >> m >> q;
    for (int i = 1; i <= m; i++) {
      read_buffer(t[i].p + 1, n);
      for (int j = 1; j <= n; j++) log("%d%c", t[i].p[j], " \n"[j == n]);
    }
    for (int op[5], i = 1; i <= q; i++) {
      read_buffer(op, 3);
      qry[op[2]].emplace_back(op[0], op[1], i);
    }
    for (int i = 1; i <= n; i++) uni[i] = i;

    vector<pair<int, int>> ext;
    auto process_ext = [&]() {
      for (int i = 1; i <= n; i++) G[i].clear();
      auto tmp = ext;
      ext.clear();
      for (const auto &[u, v] : tmp) {
        int x = find(u), y = find(v);
        if (x != y) {
          ext.emplace_back(x, y);
          G[x].push_back(y);
        }
      }
    };

    for (const auto &[a, b, k] : qry[0]) {
      ans[k] = a == b;
    }
    for (int i = 1; i <= m; i++) {
      // log(">>>>> %d <<<<<\n", i);
      if (t[i].init()) {
        // 合并额外环
        for (const auto &cir : t[i].cir) {
          log("! find cir");
          for (int x : cir) log("%d(%d) ", x, find(x));
          log("\n");
          vector<int> rts;
          for (int x : cir) rts.push_back(find(x));
          sort(all(rts));
          rts.erase(unique(all(rts)), rts.end());
          merge_all(rts);
        }
        // 添加额外边
        for (const auto &it : t[i].ext) {
          log("find ext edge : (%d, %d)\n", it.first, it.second);
          ext.push_back(it);
        }

        // 重新处理dag
        tim = cnt = 0;
        for (int i = 1; i <= n; i++)
          if (find(i) == i) {
            dfn[i] = low[i] = col[i] = 0;
          }
        process_ext();
        for (int i = 1; i <= n; i++)
          if (find(i) == i && !dfn[i]) {
            tarjan(i);
          }
        for (int i = 1; i <= cnt; i++) con[i].clear();
        for (int i = 1; i <= n; i++)
          if (find(i) == i) {
            // log("col[%d] = %d\n", i, col[i]);
            con[col[i]].push_back(i);
          }
        for (int i = 1; i <= cnt; i++) {
          merge_all(con[i]);
        }
        // 再次根据额外边缩点
        for (int i = 1; i <= n; i++)
          if (find(i) == i) {
            bit[i].reset();
            bit[i].set(i);
            deg[i] = 0;
          }
        process_ext();
        for (const auto &[u, v] : ext) deg[v]++; // 处理入度
        queue<int> q;
        for (int i = 1; i <= n; i++)
          if (find(i) == i && deg[i] == 0) {
            q.push(i);
          }
        while (q.size()) {
          int u = q.front();
          q.pop();
          for (int v : G[u]) {
            // log("[[ext edge]] %d -> %d\n", u, v);
            bit[v] |= bit[u];
            if (!--deg[v]) {
              q.push(v);
            }
          }
        }
      }
      for (auto [a, b, k] : qry[i]) {
        // log("query[%d] :: a=%d(%d) b=%d(%d) :: %d\n", k, a, find(a), b, find(b), (int)bit[b][a]);
        a = find(a);
        b = find(b);
        ans[k] = bit[a][b];
      }
    }

    for (int i = 1; i <= q; i++) cout << ans[i];
    cout << endl;
    // log("\n\n");

    for (int i = 0; i <= m + 1; i++) qry[i].clear();
  }
}