#include <bits/stdc++.h>
using namespace std;
void solve();
int main() {
  freopen("assign.in","r",stdin);
  freopen("assign.out","w",stdout);
  int tt = 1;
  cin >> tt;
  while(tt--) {
  	solve();
  }
}

#define int long long

const int Mod = 1e9 + 7;

int n,m,v,ans;
map<int,int> a;

int now1[15],now2[15];

int Check() {
  for(int i = 1;i < n;i++) {
  	if(now1[i] / 2 + 1 == now2[i] && now1[i] % 2 == now2[i + 1] - 1) {
  	  return 0;
	}
  }
  for(int i = 1;i <= n;i++) {
  	if(a[i] && a[i] != now2[i]) {
  	  return 0;
	}
  }
  return 1;
}

int DFS2(int x) {
  if(x > n) return Check();
  int ans = 0;
  now2[x] = 1,ans |= DFS2(x + 1);
  now2[x] = 2,ans |= DFS2(x + 1);
  now2[x] = 0;
  return ans;
}

void DFS1(int x) {
  if(x == n) {
  	if(DFS2(1)) {
  	  ans++;
	}
    return;
  }
  now1[x] = 1,DFS1(x + 1);
  now1[x] = 2,DFS1(x + 1);
  now1[x] = 3,DFS1(x + 1);
  now1[x] = 4,DFS1(x + 1);
  now1[x] = 0;
}

int Pow(int a,int b) {
  int ans = 1;
  a %= Mod;
  while(b) {
  	if(b & 1) ans = (ans * a) % Mod;
  	a = a * a % Mod;
  	b /= 2;
  }
  return ans;
}

void solve() {
  a.clear();
  ans = 0;
  cin >> n >> m >> v;
  int flag = 1;
  for(int i = 1,c,d;i <= m;i++) {
  	cin >> c >> d;
  	if(a[c] && a[c] != d) flag = 0;
  	a[c] = d;
  }
  if(!flag) {
  	cout << 0 << '\n';
  	return;
  }
  if(n <= 9) DFS1(1),cout << ans << '\n';
}
