#include <bits/stdc++.h>
using namespace std ;
const int MAXN=1e6+7;
const int INF = 0x3f3f3f3f;
typedef long long ll;
#define endl "\n"


void solve(){
    int n;
    cin>>n;
    vector<vector<int > > edges(n+1);
    for(int i=1;i<=n;i++){
        int u,v;
        cin>>u>>v;
        edges[u-1].push_back(v);
        edges[v].push_back(u-1);
    }
    int sum=0;
    vector<int > vis(n+1,0);
    function <void (int ) > dfs=[&](int p){
        sum++;
        for(auto t: edges[p]){
            if(vis[t]==1){
                continue;
            }
            vis[t]=1;
            dfs(t);
        }
    };
    for(int i=0;i<=n;i++){
        if(edges[i].empty()){
            continue;
        }
        if(vis[i]==1){
            continue;;
        }
        vis[i]=1;
        dfs(i);
    }
    if(sum==n+1){
        cout<<1<<endl;
    }else{
        cout<<0<<endl;
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);

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