#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int t;
	cin >> t;
	while (t--)
	{
		int n, u, v;
		cin >> n;
		vector<int> fa(n + 1);
		iota(fa.begin(), fa.end(), 0);
		function<int(int)> find = [&](int x)
		{
			return fa[x] = (fa[x] == x ? x : find(fa[x]));
		};
		for (int i = 0; i < n; i++)
		{
			cin >> u >> v;
			u = find(u - 1), v = find(v);
			if (u == v)
				break;
			fa[u] = v;
		}
		cout << ((u == v) ? 0 : 1) << "\n";
	};

	return 0;
}