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

const int N = 1000010;
int l[N], r[N];
int head[N], nxt[N << 1], to[N << 1];
int cnt = 1;
bool ok = true;
int vis[N];

// 添加边
void add_edge(int a, int b) {
    to[cnt] = b;
    nxt[cnt] = head[a];
    head[a] = cnt++;
}

// 判断是否有环
void dfs(int s, int f) {
    for (int i = head[s]; i; i = nxt[i]) {
        int nt = to[i];
        if (nt == f) continue;  // 跳过父节点
        if (vis[nt]) {  // 如果已经访问过，说明有环
            ok = false;
            return;
        }
        vis[nt] = 1;
        dfs(nt, s);
    }
}

void solve() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> l[i] >> r[i];
    }

    // 初始化
    fill(vis, vis + n + 1, 0);
    fill(head, head + n + 1, 0);
    cnt = 1;
    ok = true;

    // 构造图
    for (int i = 1; i <= n; i++) {
        add_edge(l[i] - 1, r[i]);
        add_edge(r[i], l[i] - 1);
    }

    vis[0] = 1;
    dfs(0, 0);

    if (ok) cout << 1 << '\n';
    else cout << 0 << '\n';
}

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

    int T;
    cin >> T;
    while (T--) {
        solve();
    }
}