#include<bits/stdc++.h>
using namespace std;
//#pragma GCC optimize(2)
//#pragma GCC optimize(3,"Ofast","inline")
typedef long long ll;
#define pll pair<ll,ll>
const int N=1e6+5;
ll n,f[N],ans;
ll find(ll x){
	return f[x]==x?x:f[x]==find(f[x]);
}
void solve(){
	cin>>n;
	for(int i=0;i<=n;++i)f[i]=i;
	ans=1;
	for(int i=1;i<=n;++i){
		ll l,r;cin>>l>>r;
		--l;
		if(find(l)==find(r))ans=0;
		else f[find(l)]=find(r);
	}
	cout<<ans<<endl;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;cin>>t;
    while(t--){
    	solve();
	}
    return 0;
}