#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e6 + 10;
pair<int,int> a[N], b[N];
struct P{
	int l, r;
	vector<int> c;
}tr[N * 4];

void build(int id, int l, int r){
	tr[id].l = l, tr[id].r = r;
	tr[id].c.resize(r - l + 1);
	if(l == r){
		tr[id].c[0] = b[l].second;
		return;
	}
	int mid = (l + r) >> 1, lf = id * 2, rt = id * 2 + 1;
	build(lf, l, mid); build(rt, mid + 1, r);
	int i = 0, j = 0, ct1 = mid - l + 1, ct2 = r - mid, idx = 0;
	while(i < ct1 && j < ct2){
		if(tr[lf].c[i] <= tr[rt].c[j]){
			tr[id].c[idx ++] = tr[lf].c[i ++];
		}else{
			tr[id].c[idx ++] = tr[rt].c[j ++];
		}
	}
	
	while(i < ct1){
		tr[id].c[idx ++] = tr[lf].c[i ++];
	}
	while(j < ct2){
		tr[id].c[idx ++] = tr[rt].c[j ++];
	}
}

int find_low(int id, int l, int r, int x){
	int l1 = tr[id].l, r1 = tr[id].r, mid = (l1 + r1) >> 1;
	
	if(l <= l1 && r1 <= r){
		int cnt = tr[id].c.end() - lower_bound(tr[id].c.begin(), tr[id].c.end(), x);
		return cnt;
	}
	int lf = id * 2, rt = id * 2 + 1;
	if(r <= mid){
		return find_low(lf, l, r, x);
	}else if(l >= mid + 1){
		return find_low(rt, l, r, x); 
	}else{
		return find_low(lf, l, r, x) + find_low(rt, l, r, x);
	}
	
}

void solve(){
	
	int n; cin >> n;
	
	for(int i = 0; i < n; i ++){
		cin >> a[i].first >> a[i].second;
	}
	sort(a, a + n);
	
	priority_queue<pair<int,int>,vector<pair<int,int> >, greater<pair<int,int> > > qk;
	int l = 0;
	
	for(int i = 1; i <= n; i ++){
		
		while(l < n && a[l].first <= i){
			qk.push({a[l].second, a[l].first});
			l ++;
		}
		if(qk.size() == 0){
			cout << "0";
			return;
		}else{
			int l = qk.top().second, r = qk.top().first;
			if(l <= i && i <= r){
				b[i] = {l, r};
				qk.pop();
			}else{
				cout << "0";
				return;
			}
			
		}
	}
	build(1, 1, n);
	
	int ans = 0;
	for(int i = 1; i <= n; i ++){
		
		int up = b[i].second, ed = b[i].first;
		if(ed > i - 1) continue;
		ans += find_low(1, ed, i - 1, up);
		
	}
	ans = ans % 2;
	cout << ans;
}

signed main(){
	
	ios::sync_with_stdio(NULL);
	cin.tie(0); cout.tie(0);
	
	int T; cin >> T;
	while(T --){
		solve();
		cout << '\n';
	}
    return 0;
}