#include <bits/stdc++.h>	

using ll  = long long;
using ull = unsigned long long;

using i64 = long long;
using ui64 = unsigned long long;

using pii = std::pair<int,int>; 
constexpr int mod = 1e9+7;

struct DefaultEdgeType { int to; };

template<typename E = DefaultEdgeType> struct Graph {
private:

	int n;
	std::vector<std::vector<E>> adj_;

public:
	Graph(int node_cnt) 
		: n(node_cnt), adj_(node_cnt)
	{}

	template<typename...Args>
	void to(int u, Args&&...args) {
		adj_[u].emplace_back(std::forward<Args>(args)...);
	}

	template<typename...Args>
	void connect(int u, int v, Args&&...args) {
		to(u, v, std::forward<Args>(args)...);
		to(v, u, std::forward<Args>(args)...);
	}	

	void connect(int u, int v) {
		to(u, v);
		to(v, u);
	}

	std::vector<E> & operator[](int u) {
		return adj_[u];
	}	

	const std::vector<E> & operator[](int u) const {
		return adj_[u];
	}

	int N() const {
		return n;
	}

	int size() const {
		return n;
	}
};

template<typename NT = int, typename E = DefaultEdgeType> struct GraphNt : public Graph<E> {
private :
	std::vector<NT> a_;
public : 
	GraphNt(int node_cnt) 
		: Graph<E>(node_cnt),
		a_(node_cnt)
	{}

	GraphNt(const std::vector<NT> & a) 
		: Graph<E>(a.size()),
			a_(a)
	{}	

	GraphNt(std::vector<NT> && a) 
		: Graph<E>(a.size()),
			a_(a)
	{}

	const NT & a(int u) const {
		return a_[u];
	} 	

	NT & a(int u) {
		return a_[u];
	} 
};

struct DSU {
	std::vector<int> f, sz;

	DSU() {};
	DSU(int n) {
		init(n);
	}

	void init(int n) {
		f.resize(n);
		std::iota(f.begin(), f.end(), 0);
		sz.assign(n, 1);
	}

	int find(int x) {
		while (f[x] != x) {
			x = f[x] = f[f[x]];
		}

		return x;
	}

	bool merge(int x, int y) {
		x = find(x);
		y = find(y);
		if (x == y) {
			return false;
		}

		if (sz[x] < sz[y]) {
			std::swap(x, y);
		}

		sz[x] += sz[y];
		f[y] = x;
		return true;

	}

	int size(int x) {
		return sz[find(x)];
	}

	bool same(int x, int y) {
		return find(x) == find(y);
	}
};

std::vector<int> decode(std::string & s) {
	int n = s.size() / 2;
	std::vector<int> v(n);
	for (int i = 0; i < n; i ++) {
		v[i] = (s[2 * i] - 48) * 50 + s[2 * i + 1] - 48;
	}

	return v;
}

struct Edge {
	int to;
	int w;
};

void solve() {
	int n, m, q; std::cin >> n >> m >> q;
	Graph<Edge> g(n);
	DSU uf(n);
	for (int i = 1; i <= m; i ++) {
		std::string s; std::cin >> s;
		std::vector<int> edges = decode(s);
		
		std::vector<int> cnt(n);
		
		int siz = 0;
		for (auto & v : edges) cnt[--v] ++;
		for (auto & v : cnt) siz += (v > 0);

		if (siz == n) {
			for (int j = 0; j < n; j ++) {
				if (uf.find(j) != uf.find(edges[j])) {
					uf.merge(j, edges[j]);
					g.connect(j, edges[j], i);
				}
			}
		} else if (siz == n - 1) {
			int cnt0 = -1, cnt2 = -1;
			for (int j = 0; j < n; j ++) {
				if (cnt[j] == 0) cnt0 = j;
				if (cnt[j] == 2) cnt2 = j;
			}

			for (int j = 0; j < n; j ++) {
				if (edges[j] == cnt2) {
					g.to(j, cnt0, i);
				}
			}
		}
	}	


	std::priority_queue<std::pair<int,int>, std::vector<std::pair<int,int>>, std::greater<>> pq;
	std::vector<std::vector<int>> cost(n, std::vector<int>(n, m + 1));
	for (int i = 0; i < n; i ++) cost[i][i] = 0;
	for (int i = 0; i < n; i ++) {
		pq.emplace(0, i);
		while (!pq.empty()) {
			auto [ti, u] = pq.top(); pq.pop();
			if (cost[i][u] < ti) continue;
			for (auto [v, w] : g[u]) {
				if (cost[i][v] > std::max(ti, w)) {
					cost[i][v] = std::max(ti, w);

					pq.emplace(cost[i][v], v);
				}	
			}
		}
	}

	std::string res(q, '0');
	for (int i = 0; i < q; i ++) {
		std::string s; std::cin >> s;
		std::vector<int> queries = decode(s);
		if (cost[queries[0] - 1][queries[1] - 1] <= queries[2]) {
			res[i] ++;
		}
	}

	std::cout << res << '\n';
}

int main()
{
	
	std::ios::sync_with_stdio(false);
	std::cin.tie(0); std::cout.tie(0);		
		
	int t = 1; 
	std::cin >> t;
	
	while (t -- > 0) {
		solve();
	}

	return 0;
}