#include <iostream>
#include <cstring>
#include <queue>
#include <map>
#include <set>
#include <algorithm>
#include <cmath>
#include <vector>
#include <stack>
#include <unordered_set>
using namespace std;
typedef long long LL;
typedef pair<LL,LL> PII;//开long long，求求你了，记得开long long 
const LL N=1e6+10;
const LL INF=1e18;
const double small=1e-16;
//千万不要用puts()和gets()，求求你了 
LL n;
int h[N];
int e[2*N],ne[2*N],idx;
unordered_set<int> has;
bool st[N];
int ans=0;

void add(int x,int y)
{
	e[idx]=y;
	ne[idx]=h[x];
	h[x]=idx++;
	
}

void dfs(int u)
{
	if(st[u]==0)
		{
			ans++;
			st[u]=1;
		}
	for(int i=h[u];i!=-1;i=ne[i])
	{
		int k=e[i];
		if(!st[k])
		{
			dfs(k);
		}
	}
}

void solve()
{
	cin>>n;
	memset(h,-1,sizeof h);
	memset(st,false,sizeof st);
	ans=0;
	idx=0;
	for(int i=1;i<=n;i++)
	{
		int x,y;
		cin>>x>>y;
		add(x-1,y);
		add(y,x-1);
		has.insert(x-1);
		has.insert(y);
	}
	dfs(0);
	if(ans==n+1)cout<<"1"<<endl;
	else cout<<"0"<<endl;
}

int main()
{
    
	int t=1;
	cin>>t;
	while(t--)
	{
		solve();
	}
	return 0;
}