#include<bits/stdc++.h>

using namespace std;
using ll = long long;

constexpr int N = 1E6+10;
typedef pair<int, int> pii;

vector<int> e[N];
int n, p[N];
bool vis[N];

int fd(int x) {
    if (p[x] != x) p[x] = fd(p[x]);
    return p[x];
}

void mg(int a, int b) {
    int pa = fd(a), pb = fd(b);
    if (pa != pb) {
        p[pa] = pb;
    }
}

bool check() {
    int pa = fd(1);
    for (int i = 1; i <= n+1; i ++) {
        if (fd(i) != pa) {
            //cout << "111" << endl;
            return false;
        }
    }
    queue<pii> q;
    q.push({1, 0});
    while (!q.empty()) {
        auto t = q.front(); q.pop();
        int u = t.first, fa = t.second;
        vis[u] = true;
        for (int v : e[u]) {
            if (v == fa) continue;
            if (vis[v]) {
                //cout << 222 << endl;
                return false;
            }
            q.push({v, u});
        }
    }
    return true;
}

void solve() {
    cin >> n;
    for (int i = 1; i <= n+1; i ++) {
        p[i] = i;
        e[i] = {};
    }
    for (int i = 1; i <= n; i ++) {
        int a, b; cin >> a >> b;
        b ++;
        mg(a, b);
        e[a].emplace_back(b);
        e[b].emplace_back(a);
    }
    if (check()) cout << 1 << endl;
    else cout << 0 << endl;
}

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

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