#include <bits/stdc++.h>
#include <vector>
#include <algorithm>

using namespace std;

int compute_parity(int n, vector<pair<int, int>>& intervals) {
    // 使用向量数组来表示稀疏矩阵，每行存储非零元素的列索引
    vector<set<int>> M(n);
    for (int i = 0; i < n; ++i) {
        int l_i = intervals[i].first;
        int r_i = intervals[i].second;
        for (int j = l_i - 1; j <= r_i - 1; ++j) { // 调整索引为 0 开始
            M[i].insert(j);
        }
    }

    int det = 1;
    for (int i = 0; i < n; ++i) {
        // 寻找主元
        int pivot_row = -1;
        for (int j = i; j < n; ++j) {
            if (M[j].count(i)) {
                pivot_row = j;
                break;
            }
        }
        if (pivot_row == -1) {
            det = 0;
            break;
        }
        if (pivot_row != i) {
            swap(M[i], M[pivot_row]);
            det *= -1; // 交换行改变行列式的符号
        }
        // 消元
        for (int j = i + 1; j < n; ++j) {
            if (M[j].count(i)) {
                // 在 GF(2) 上，减法等价于按位异或
                set<int> new_row;
                auto it1 = M[j].begin();
                auto it2 = M[i].begin();
                while (it1 != M[j].end() || it2 != M[i].end()) {
                    if (it2 == M[i].end() || (it1 != M[j].end() && *it1 < *it2)) {
                        new_row.insert(*it1);
                        ++it1;
                    } else if (it1 == M[j].end() || *it2 < *it1) {
                        new_row.insert(*it2);
                        ++it2;
                    } else {
                        // 相同的元素，异或后为 0，跳过
                        ++it1;
                        ++it2;
                    }
                }
                M[j] = new_row;
            }
        }
    }
    return (det + 2) % 2; // 确保结果为非负数
}

namespace FAST_IO{
	#define ll long long
	#define ull unsigned long long
	#define db double
	#define _8 __int128_t
	#define Get() (BUF[Pin++])
	const int LEN=1<<20;
	char BUF[LEN];
	int Pin=LEN;
	inline void flushin(){memcpy(BUF,BUF+Pin,LEN-Pin),fread(BUF+LEN-Pin,1,Pin,stdin),Pin=0;return;}
	inline char Getc(){return (Pin==LEN?(fread(BUF,1,LEN,stdin),Pin=0):0),BUF[Pin++];}
	template<typename tp>inline tp read(){(Pin+40>=LEN)?flushin():void();tp res=0;char f=1,ch=' ';for(;ch<'0'||ch>'9';ch=Get())if(ch=='-')f=-1;for(;ch>='0'&&ch<='9';ch=Get())res=(res<<3)+(res<<1)+ch-48;return res*f;}
	template<typename tp>inline void read(tp &n){(Pin+40>=LEN)?flushin():void();tp res=0;char f=1,ch=' ';for(;ch<'0'||ch>'9';ch=Get())if(ch=='-')f=-1;for(;ch>='0'&&ch<='9';ch=Get())res=(res<<3)+(res<<1)+ch-48;n=res*f;return;}
	inline int readstr(char *s){int len=0;char ch=Getc();while(!isalnum(ch))ch=Getc();while(isalnum(ch))s[len++]=ch,ch=Getc();return len;}
	#define Put(x) (PUF[Pout++]=x)
	char PUF[LEN];
	int Pout;
	inline void flushout(){fwrite(PUF,1,Pout,stdout),Pout=0;return;}
	inline void Putc(char x){if(Pout==LEN)flushout(),Pout=0;PUF[Pout++]=x;}
	template<typename tp>inline void write(tp a,char b='\n'){static int stk[40],top;(Pout+50>=LEN)?flushout():void();if(a<0)Put('-'),a=-a;else if(a==0)Put('0');for(top=0;a;a/=10)stk[++top]=a%10;for(;top;--top)Put(stk[top]^48);Put(b);return;}
	inline void wt_str(string s){for(char i:s)Putc(i);return;}
}
using namespace FAST_IO;
int main() {
    int n;
    int T;
    read(T);
    while(T--)
    {
    	read(n);
	    vector<pair<int, int>> intervals(n);
	    for (int i = 0; i < n; ++i) {
	        int l_i, r_i;
	        read(l_i),read(r_i);
	        intervals[i] = {l_i, r_i};
	    }
	    int result = compute_parity(n, intervals);
	    write(result);
	}
	flushout();
    return 0;
}