//
// Created by 35263 on 2024/9/16.
//
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1000005;
vector<int>g[maxn];
int n,m,l,r,flag,vis[maxn];
void update(){
    for(int i=1;i<=n;i++)g[i].clear(),vis[i]=0;
    flag=false;
}
void dfs(int x,int fa){
    vis[x]=1;
    if(flag)return;
    for(auto v:g[x]){
        if(v==fa)continue;
        if(vis[v]){
            flag=true;
            return;
        }
        dfs(v,x);
    }
}
void init(){
    cin>>n;
    update();
    for(int i=1;i<=n;i++)cin>>l>>r,g[l].push_back(r),g[r].push_back(l);
    dfs(1,0);
    if(flag){
        cout<<0<<endl;
    }
    else{
        cout<<1<<endl;
    }
}
int main(){
    int t;
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin>>t;
    while(t--){
        update();
        init();
    }
    return 0;
}