#include <iostream>
#include <cstring>
using namespace std;

const int N = 1e5 + 10;
int x[N];
int c[N], d[N];
bool st[2];

int run(int ans, int n, int v){
	x[n + 1] = 1;
	for(int a = 1; a <= 2; a++){
		for(int b = 1; b <= 2; b++){
			if(a != x[1] || b != x[1] || a != x[2] || b != x[2]){
				continue;
			}else if(x[1] == 0 || x[2] == 0){
				ans++;
			}else{
				ans++;
			}
		}
	}
	return ans;
}

/*int runB(){
	
}*/

void first(int m){
	for(int j = 0; j < m; j++){
		x[c[j]] = d[j];
	}
}

int main(){
	int T;
	cin >> T;
	while(T--){
		int n, m, v;
		cin >> n >> m >> v;
		int no = 0;
		for(int i = 0; i < m ; i++){
			cin >> c[i] >> d[i];
			if(c[i] == c[i - 1]){
				no = 1;
			}
		}
		first(m);
		if(no){
			cout << 0 << endl;
			continue;
		}
		/*for(int i = 1; i <= n; i++){
			cout << x[i] << " ";
		}*/
		cout << run(0, n, v) << endl;
	}
	return 0;
}

/*
3
2 1 2
1 1
2 2 2
1 1
2 2
2 2 2
1 1
1 2


*/

/*
1
2 1 2
1 1

4
*/
