#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#define init(x) memset (x,0,sizeof (x))
#define ll long long
#define ull unsigned long long
#define INF 0x3f3f3f3f
using namespace std;
const int MAX = 1e6 + 5;
const int MOD = 1e9 + 7;
inline int read ();
struct node
{
	int l,r;
} f[MAX];
int t,n,ok,cnt,ans,vis[MAX];
bool cmp (node x,node y)
{
	if (x.l == y.l) return x.r < y.r;
	return x.l < y.l;
} 
void solve (int x);
int main ()
{
	//freopen (".in","r",stdin);
	//freopen (".out","w",stdout);
	t = read ();
	while (t--)
	{
		n = read ();ok = cnt = ans = 0;
		for (int i = 1;i <= n;++i) vis[i] = 0,f[i].l = read (),f[i].r = read ();
		sort (f + 1,f + 1 + n,cmp);
		for (int i = 1;i <= n;++i)
		{
			if (f[i].l >= f[i - 1].r) ++cnt;
			if (f[i].l == f[i - 1].l && f[i].r == f[i - 1].r) {puts ("0");ok = 1;break;}
		}
		if (ok) continue;
		if (cnt >= min (n,n / 2 + n / 5)) puts ("1");
		else if (n <= 15) 
		{
			solve (1);
			printf ("%d\n",ans % 2);
		}
		else puts ("0");
	}
	return 0;
}
inline int read ()
{
    int s = 0;int f = 1;
    char ch = getchar ();
    while ((ch < '0' || ch > '9') && ch != EOF)
	{
        if (ch == '-') f = -1;
        ch = getchar ();
    }
    while (ch >= '0' && ch <= '9')
	{
        s = s * 10 + ch - '0';
        ch = getchar ();
    }
    return s * f;
}
void solve (int x)
{
	if (x == n + 1)
	{
		++ans;
		return ;
	}
	for (int i = f[x].l;i <= f[x].r;++i)
	{
		if (vis[i]) continue;
		vis[i] = 1;
		solve (x + 1);
		vis[i] = 0;
	}
}