#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define debugging 1
const int maxn = 2010;
#define pii pair<int, int>
#define f first
#define s second
#define mp make_pair
#define inf 0x3f3f3f3f

int n, l, q;
int f[maxn];
int a[maxn];
int vis[maxn];
int dis[maxn];
queue<int> que[maxn];
int ans[maxn][maxn];
vector<pii> g[maxn];
string s;
int u, v, w;

int find(int x) {
	return x == f[x] ? x : f[x] = find(f[x]);
}
void merge(int u, int v, int id) {
	int fu = find(u);
	int fv = find(v);
	if (fu != fv) {
		f[fu] = fv;
		g[u].push_back(mp(v, id));
		g[v].push_back(mp(u, id));
	}
}

void init() {
	for (int i = 1; i <= n; ++i) {
		f[i] = i;
		g[i].clear();
	}
}
int get_val(int id) {
	return (s[id*2] - 48) * 50 + (s[id*2+1] - 48);
}


void solve() {
	cin >> n >> l >> q;
	init();
	
	for (int i = 1; i <= l; ++i) {
		cin >> s;
		for (int j = 1; j <= n; ++j) {
			vis[j] = 0;
		}
		int sz = 0;
		for (int j = 1; j <= n; ++j) {
			int id = j - 1;
			a[j] = get_val(j - 1);
			if (vis[a[j]]++ == 0) {
				++sz;
			}
		}
		if (sz <= n - 2) { // collide 
			continue;
		}
		if (sz == n) {
			for (int j = 1; j <= n; ++j) {
				merge(j, a[j], i);
			}
			continue;
		} 
		// sz == n - 1
		int x0 = -1, x2 = -1;
		for (int j = 1; j <= n; ++j) {
			if (vis[j] == 0) {
				x0 = j;
			}
			if (vis[j] == 2) {
				x2 = j;
			}
		}
		for (int j = 1; j <= n; ++j) {
			if (a[j] == x2) {
				g[j].push_back(mp(x0, i));
			}
		}
	}
	
	// 预处理 
	for (int st = 1; st <= n; ++st) {
		for (int i = 1; i <= n; ++i) {
			dis[i] = inf;
			vis[i] = 0;
		} 
		for (int rd = 1; rd <= l; ++rd) {
			while (!que[rd].empty()) {
				que[rd].pop();
			}
		}
		dis[st] = 0;
		que[0].push(st);
		for (int rd = 0; rd <= l; ++rd) {
			while (!que[rd].empty()) {
				u = que[rd].front();
				que[rd].pop();
				if (vis[u]) {
					continue;
				}
				vis[u] = 1;
				
				for (auto p: g[u]) {
					v = p.f;
					w = p.s;
					int mx = max(dis[u], w);
					if (dis[v] > mx) {
						dis[v] = mx;
						que[mx].push(v);
					}
				}
			}
		}
		for (int i = 1; i <= n; ++i) {
			ans[st][i] = dis[i];
		}
	}
	
	string res('0', q);
	for (int i = 1; i <= q; ++i) {
		cin >> s;
		for (int j = 1; j <= 3; ++j) {
			a[j] = get_val(j - 1);
		}
		res[i-1] = ans[a[1]][a[2]] <= a[3] ? '1' : '0';
		
	}
	cout << res << endl;
}

int main() {
    int tt = 1;
    cin >> tt;
//    scanf("%d", &tt);
    while (tt--) {
        solve();
    }
    
    return 0;
}
/*
9
4
5 5 3 5
1: [1, 1]
2: [2, 2]
3: [3, 3]
4: [3, 4]
1
*/