#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
const int INF = 0x3f3f3f3f;
const i64 mod = 1e9 + 7;
const int N = 1000005;
i64 n;
int head[N], nxt[2*N], to[2*N], cnt;
void add(int u, int v) {
    nxt[++cnt] = head[u];
    head[u] = cnt;
    to[cnt] = v;
}
bool vis[N], ok;
void dfs(int cur, int id) {
    vis[cur] = 1;
    
    for(int i = head[cur]; i; i = nxt[i]) {
        if(ok == 0) return;
        if((i^id) == 1) continue;
        int v = to[i];
        if(vis[v]) {
            ok = 0;
            return;
        }
        dfs(v, i);
    }
}
void solve() {
    cin >> n;
    ok = 1;
    cnt = 1;
    for(int i = 1; i <= n+1; ++i) {
        vis[i] = 0;
        head[i] = 0;
    }
    for(int i = 1; i <= n; ++i) {
        int u, v;
        cin >> u >> v;
        add(u, v+1);
        add(v+1, u);
    }
    dfs(1, 0);
    cout << (ok ? 1 : 0) << '\n';
};
int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    int t;
    cin >>t;
    while(t--) {
        solve();
    }
    return 0;
}