//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
const int kN = 1e6 + 10;
//=============================================================
int n, fa[kN];
//=============================================================
int find(int x_) {
  return fa[x_] == x_ ? x_ : fa[x_] = find(fa[x_]);
}
void merge(int x_, int y_) {
  int fx = find(x_), fy = find(y_);
  if (fx == fy) return ;
  fa[fx] = fy;
}
//=============================================================
int main() {
  //freopen("1.txt", "r", stdin);
  std::ios::sync_with_stdio(0), std::cin.tie(0);
  int T; std::cin >> T;
  while (T --) {
    std::cin >> n;
    for (int i = 0; i <= n; ++ i) fa[i] = i;
    int ans = 1;
    for (int i = 1; i <= n; ++ i) {
      int l, r; std::cin >> l >> r;
      if (find(l) == find(r)) ans = 0;
      merge(l, r);
    }
    std::cout << ans << "\n";
  }
  return 0;
}