#include <bits/stdc++.h>
using namespace std;

const int mod = 1e9 + 7;

struct Limit
{
	int c, d;
};

void sub1(int n, int m, int v) {
	vector<Limit> lim(m + 1);
	for (int i = 1; i <= m; i++) {
		cin >> lim[i].c >> lim[i].d;
	}
	vector<int> a(n + 1, 0), b(n + 1, 0); // n - 1 stricted limit
	int ans = 0;
	for (int i = 1; i <= 1 << (n - 1); i++) {
		int __x = i, p = 1;
		while (__x) {
			a[p] = (__x % 2) + 1;
			__x /= 2;
			p++;
		}
		for (int j = 1; j <= 1 << (n - 1); j++) {
			__x = j, p = 1;
			while (__x) {
				b[p] = (__x % 2) + 1;
				__x /= 2;
				p++;
			}
			vector<int> x(n + 1);
			for (int k = 1; k <= m; k++) {
				if (x[lim[k].c]) {
					cout << "0\n";
					return;
				}
				x[lim[k].c] = lim[k].d;
			}
			for (int k = 1; k <= n; k++) {

			}
		}
		
		// if x[i] == a[i]: x[i + 1] = b[i]
	}
	cout << ans;
}

void sub2(int n, int m, int v) {
	vector<Limit> lim(m);
	for (int i = 0; i < m; i++) {
		cin >> lim[i].c >> lim[i].d;
	}
	cout << "0\n";
}

void sub3(int n, int m, int v) {
	vector<Limit> lim(m);
	for (int i = 0; i < m; i++) {
		cin >> lim[i].c >> lim[i].d;
	}
	cout << "0\n";
}

void test() {
	int n, m, v;
	cin >> n >> m >> v;
	if (v == 2) sub1(n, m, v);
	else if (m == 1) sub2(n, m, v);
	else /*if (m == n)*/ sub3(n, m, v);
	return;
}

int main() {
	freopen("assign.in", "r", stdin);
	freopen("assign.out", "w", stdout);
	ios::sync_with_stdio(false);
	int t;
	cin >> t;
	while (t--) test();
	return 0;
}