#include<bits/stdc++.h>
using namespace std;
using ll = long long;
//#define int ll
void solve()
{
       int n;
       cin>>n;
       vector<vector<int>>g(n+1);
       for(int i=1;i<=n;i++)
       {
       		int l,r;
       		cin>>l>>r;
       		l--;
       		g[l].push_back(r);
       		g[r].push_back(l);
       }
       vector<int>vis(n+1);
       int f=1;
       auto dfs=[&](auto self,int u,int  fa)->void
       {
       		if(vis[u]==0)
       		{
       			vis[u]=1;
       			for(auto v:g[u])
       			{
       				if(v!=fa)
       				{
       					self(self,v,u);
       				}
       			}
       		}
       		else
       		{
       			f=0;
       		}
       };
       dfs(dfs,0,-1);
       cout<<f<<"\n";
}
signed main()
{
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int t = 1;
    cin >> t;
    while (t--)
    {
        solve();
    }
}