#include<iostream>
using namespace std;

int n, t;
int fa[1000010];

void init(int n){
    for(int i = 1;i<=n;i++){
        fa[i] = i;
    }
}

int find(int x){
    return fa[x] == x?x:fa[x] = find(fa[x]);
}

void merge(int x,int y){
    int fx  = find(x),fy = find(y);
    fa[fx] = fy;
}

bool same(){
    for(int i = 0;i<=n;i++){
        if(find(i) != find(1))return 0;
    }
    return 1;
}

void solve(){
    cin>>n;
    init(n);
    for(int i = 1;i<=n;i++){
        int u, v;
        cin>>u>>v;
        merge(u-1, v);
    }
    cout<<same()<<endl;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>t;
    while(t--){
        solve();
    }
    return 0;
}