bool M1;
#define look_memory cerr<<abs(&M2-&M1)/1024.0/1024<<" MB\n"
#define look_time cerr<<(clock()-Time)*1.0/CLOCKS_PER_SEC<<'\n'
#include <cstdio>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <cstring>
#include <array>
#include <algorithm>
#include <queue>
#include <vector>
#include <bitset>
#include <ctime>
#include <cstdlib>
#include <random>
#include <set>
#include <ctime>
#include <map>
#include <stack>
#include <unordered_map>
#include <assert.h>
#include <unordered_set>
#define i128 __int128
#define ll long long
#define uint unsigned
#define ull unsigned long long
#define ld long double
#define fo(a,b,c) for(ll a=b;a<=c;++a)
#define re(a,b,c) for(ll a=b;a>=c;--a)
#define pii pair<ll,ll>
#define pdd pair<db,db>
#define fi first
#define pb push_back
#define se second
#define ite set<array<ll,3>> ::iterator
#define vite vector<ll> ::iterator
#define mite map<ll,ll> ::iterator
using namespace std;
const ll mod=998244353;
inline ll gi()
{
	ll x = 0, f = 1;
	char ch = getchar();
	while(ch < '0' || ch > '9')
	{
		if (ch == '-')
			f = -1;
		ch = getchar();
	}
	while(ch >= '0' && ch <= '9')
	{
		x = (x<<1) + (x<<3) + (ch^48);
		ch = getchar();
	}
	return x * f;
}
ll _=1;
const ll inf=2e17+5,iinf=1e9+5;
const ll N=1000005;
ll d[N],l[N],r[N];
ll jj(ll id1,ll id2)
{
	ll zl=max(l[id1],l[id2]),zr=min(r[id1],r[id2]);
	ll ans=max(0ll,zr-zl+1);
	return ans%2;
}
void sol()
{
	ll os=0;
	ll n=gi();
	fo(i,1,n) d[i]=0;
	fo(i,1,n)
	{
		l[i]=gi(),r[i]=gi();
		if((r[i]-l[i]+1)%2==0) os++;
	}
	if(os>=3)
	{
		cout<<0;
		return;
	}
	if(os==2)
	{
		ll fid=0,sid=0;
		fo(i,1,n)
		{
			if((r[i]-l[i]+1)%2==0)
			{
				if(fid==0) fid=i;
				else sid=i;
			}
		}
		cout<<jj(fid,sid);
		return;
	}
	if(os==1)
	{
		ll id=0;
		fo(i,1,n)
		{
			if((r[i]-l[i]+1)%2==0) id=i;
			else d[l[i]]++,d[r[i]+1]--;
		}
		ll ans=0;
		fo(i,1,n)
		{
			d[i]+=d[i-1];
			if(i>=l[id]&&i<=r[id])
			{
				ans+=d[i];
			}
		}
		ans%=2;
		cout<<ans;
		return;
	}
	fo(i,1,n)
	{
		d[l[i]]++,d[r[i]+1]--;
	}
	ll ans=0;
	fo(i,1,n)
	{
		d[i]+=d[i-1];
		ll num=d[i];
		ans+=num*(num-1)/2;
		ans%=2;
	}
	cout<<ans;
}
bool M2;
int main()
{
	int Time=clock();
	look_memory;
	_=gi();
	while(_--)
	{
		sol();
		printf("\n");
	}
	look_time;
	return 0;
}