#include <bits/stdc++.h>

using i64 = long long;
const int N = 1e6 + 10;

int p[N];

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

void solve() {
	int n;
	std::cin >> n;
	for (int i = 0; i <= n; i++) {
		p[i] = i;
	}
	for (int i = 0; i < n; i++) {
		int x, y;
		std::cin >> x >> y;
		x = find(x - 1), y = find(y);
		if(x == y) {
			std::cout << 0 << '\n';
			return;
		}
		p[x] = y;
	}
	std::cout << 1 << '\n';
}

int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(0), std::cout.tie(0);

	int t;
	std::cin >> t;
	while (t--) {
		solve();
	}

	return 0;
}