#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, flg = 1;
		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--;
			u = find(u), v = find(v);
			flg = (find(u) != find(v));
			fa[u] = v;
		}
		cout << flg << "\n";
	};

	return 0;
}