#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int N = 1e6 + 10;
const int MOD = 998244353;
typedef pair<ll, ll> PLL;
typedef pair<int, int > PII;
typedef pair<double, double> PDD;
ll n, zu[N];
pair<ll, ll>s[N];
ll find(ll x) { return x == zu[x] ? x : zu[x] = find(zu[x]); }
void solve(){
	cin >> n;
	for (int i = 1; i <= n + 1; i++)
		zu[i] = i;
	for (int i = 1; i <= n; i++)
	{
		cin >> s[i].first >> s[i].second;
		//s[i].second++;
	}
	for (int i = 1; i <= n; i++)
	{
		ll x = find(s[i].first), y = find(s[i].second);
		if (x == y)
		{
			cout << "0\n";
			return;
		}
		zu[x] = y;
	}
	cout << "1\n";
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	int T = 1;
	cin >> T;
	while (T--){
		solve();
	}
	return 0;
}