#include<bits/stdc++.h> 
#define int long long 
using namespace std;   
const int N=2e6+10;
pair<int,int> s[N];
int f[N];
int find(int x)
{
	return f[x]==x?x:find(f[x]);
}

void merge(int x,int y)
{
	int fx,fy;
	fx=find(x);
	fy=find(y);
	if(fx!=fy) f[fx]=fy;
}

signed main() 
{  
    ios::sync_with_stdio(0);  
    cin.tie(0);  
    cout.tie(0);  
    int _=1;  
    cin>>_;  
    while(_--) 
	{  
		int n;
		cin>>n;
		bool fl=0;
		int k=1;
		for(int i=1;i<=n+1;i++)
		{
			f[i]=i;
		}
		for(int i=1;i<=n;i++)
		{
			cin>>s[i].first>>s[i].second;
			s[i].second++;
		}
		for(int i=1;i<n;i++)
		{
			int x=find(s[i].first),y=find(s[i].second);
			if(x==y)
			{
				k++;
			}
			merge(x,y);
		}
		if(k==1) cout<<1<<endl;
		else cout<<0<<endl;
	}
    return 0;  
}