#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define fi first
#define se second
#define pb push_back
#define pii pair<int,int>
#define desc greater<int>
#define sz(v) (int)v.size()
#define sc(a) cout<<a<<endl;return
#define all(v) v.begin(),v.end()
#define popcount __builtin_popcount
#define mem(a,v) memset(a,(v),sizeof(a))
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define rep_(i,a,b) for(int i=a;i>=b;i--)
#define de(a) cerr<<"DEBUG:"<<(a)<<'\n'
#define de2(a,b) cerr<<"DEBUG:"<<(a)<<' '<<(b)<<'\n'
#define SET(a)  cout<<fixed<<setprecision((a))
#define Mint(x) x=(x%mod+mod)%mod
#define endl '\n'
#define eps 1e-6
#define PI  acos(-1)

const int inf = INT_MAX;
const ll  INF = 0x3f3f3f3f3f3f3f3f;
ll gcd(ll a,ll b) {return b==0?a:gcd(b,a%b);}
bool isprime(ll x){for(ll i=2;i*i<=x;i++){if(x%i==0) return 0;}return 1;}
ll qpow(ll a,ll b,ll p=INF){ll s=1;while(b){if(b&1)s=(s*a)%p;b>>=1;a=(a*a)%p;}return s;}


const int N = 2e6+10,M=N;
const int mod=998244353;
// typedef modint<mod> mint;
// #define int ll
set<int> g[N];
int vis[N];
bool dfs(int x,int fa){
    vis[x]=1;
    for(int y : g[x]){
        if(y==fa) continue;
        if(vis[y]) return true;
        if(dfs(y,x)) return true;
    }
    return false;
}
void solve(){
    int rt=-1,f=-1,l,r,n;
    cin>>n;
    rep(i,1,n){
        cin>>l>>r;
        if(rt==-1) rt=l;
        if(g[l].count(r+1)){
            f=0;
        }
        g[l].insert(r+1);
        g[r+1].insert(l);
    }
    if(f==0){
        cout<<"0\n";
    }else{
        cout<<!dfs(rt,-1)<<endl;
    }
    rep(i,1,n+1) g[i].clear(),vis[i]=false;
}
signed main(){
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    int T = 1;
    cin >> T;
    rep(_,1,T){
        // cout<<"Case #"<<_<<": ";
        solve();
    }
    return 0;
}