#include<bits/stdc++.h>

using namespace std;

static struct FastInput {
  static constexpr int BUF_SIZE = 1 << 20;
  char buf[BUF_SIZE];
  size_t chars_read = 0;
  size_t buf_pos = 0;
  FILE *in = stdin;
  char cur = 0;
 
  inline char get_char() {
    if (buf_pos >= chars_read) {
      chars_read = fread(buf, 1, BUF_SIZE, in);
      buf_pos = 0;
      buf[0] = (chars_read == 0 ? -1 : buf[0]);
    }
    return cur = buf[buf_pos++];
  }
  
  template <typename T>
  inline void tie(T) {}
 
  inline explicit operator bool() {
    return cur != -1;
  }
 
  inline static bool is_blank(char c) {
    return c <= ' ';
  }
 
  inline bool skip_blanks() {
    while (is_blank(cur) && cur != -1) {
      get_char();
    }
    return cur != -1;
  }
 
  inline FastInput& operator>>(char& c) {
    skip_blanks();
    c = cur;
    get_char();
    return *this;
  }
  
  inline FastInput& operator>>(string& s) {
    if (skip_blanks()) {
      s.clear();
      do {
        s += cur;
      } while (!is_blank(get_char()));
    }
    return *this;
  }
 
  template <typename T>
  inline FastInput& read_integer(T& n) {
    // unsafe, doesn't check that characters are actually digits
    n = 0;
    if (skip_blanks()) {
      int sign = +1;
      if (cur == '-') {
        sign = -1;
        get_char();
      }
      do {
        n += n + (n << 3) + cur - '0';
      } while (!is_blank(get_char()));
      n *= sign;
    }
    return *this;
  }
 
  template <typename T>
  inline typename enable_if<is_integral<T>::value, FastInput&>::type operator>>(T& n) {
    return read_integer(n);
  }
  
  #if !defined(_WIN32) || defined(_WIN64)
  inline FastInput& operator>>(__int128& n) {
    return read_integer(n);
  }
  #endif
 
  template <typename T>
  inline typename enable_if<is_floating_point<T>::value, FastInput&>::type operator>>(T& n) {
    // not sure if really fast, for compatibility only
    n = 0;
    if (skip_blanks()) {
      string s;
      (*this) >> s;
      sscanf(s.c_str(), "%lf", &n);
    }
    return *this;
  }
} fast_input;
 
#define cin fast_input
 
static struct FastOutput {
  static constexpr int BUF_SIZE = 1 << 20;
  char buf[BUF_SIZE];
  size_t buf_pos = 0;
  static constexpr int TMP_SIZE = 1 << 20;
  char tmp[TMP_SIZE];
  FILE *out = stdout;
 
  inline void put_char(char c) {
    buf[buf_pos++] = c;
    if (buf_pos == BUF_SIZE) {
      fwrite(buf, 1, buf_pos, out);
      buf_pos = 0;
    }
  }
 
  ~FastOutput() {
    fwrite(buf, 1, buf_pos, out);
  }
 
  inline FastOutput& operator<<(char c) {
    put_char(c);
    return *this;
  }
 
  inline FastOutput& operator<<(const char* s) {
    while (*s) {
      put_char(*s++);
    }
    return *this;
  }
 
  inline FastOutput& operator<<(const string& s) {
    for (int i = 0; i < (int) s.size(); i++) {
      put_char(s[i]);
    }
    return *this;
  }
 
  template <typename T>
  inline char* integer_to_string(T n) {
    // beware of TMP_SIZE
    char* p = tmp + TMP_SIZE - 1;
    if (n == 0) {
      *--p = '0';
    } else {
      bool is_negative = false;
      if (n < 0) {
        is_negative = true;
        n = -n;
      }
      while (n > 0) {
        *--p = (char) ('0' + n % 10);
        n /= 10;
      }
      if (is_negative) {
        *--p = '-';
      }
    }
    return p;
  }
 
  template <typename T>
  inline typename enable_if<is_integral<T>::value, char*>::type stringify(T n) {
    return integer_to_string(n);
  }
 
  #if !defined(_WIN32) || defined(_WIN64)
  inline char* stringify(__int128 n) {
    return integer_to_string(n);
  }
  #endif
 
  template <typename T>
  inline typename enable_if<is_floating_point<T>::value, char*>::type stringify(T n) {
    sprintf(tmp, "%.17f", n);
    return tmp;
  }
 
  template <typename T>
  inline FastOutput& operator<<(const T& n) {
    auto p = stringify(n);
    for (; *p != 0; p++) {
      put_char(*p);
    }
    return *this;
  }
} fast_output;
 
#define cout fast_output


const int N = 1e6 + 10;
int n;
std::multiset<int> l[N], r[N], tmp;
std::multiset<std::pair<int, int>> lp, rp;
template<class T>
void erase(std::multiset<T>& st, const T& val) {
  if(auto v = st.find(val); v != st.end()) {
    st.erase(v);
  }
}
void del(int li, int ri){
  erase(lp, {l[li].size(), li});
  erase(rp, {r[ri].size(), ri});
  erase(l[li], ri);
  erase(r[ri], li);
  lp.insert({l[li].size(), li});
  rp.insert({r[ri].size(), ri});
}
void add(int li, int ri){
  erase(lp, {l[li].size(), li});
  erase(rp, {r[ri].size(), ri});
  l[li].insert(ri);
  r[ri].insert(li);
  lp.insert({l[li].size(), li});
  rp.insert({r[ri].size(), ri});
}
int work() {
  while(true) {
    if(lp.rbegin()->first >= rp.rbegin()->first) {
      auto mx = *lp.rbegin();
      if(mx.first == 1) {
        return 1;
      }
      auto mxl = mx.second;
      lp.erase(mx);
      int las = mxl;
      tmp.clear();
      tmp.swap(l[mxl]);
      for(auto rit = tmp.begin(); rit != tmp.end(); ++rit) {
        auto ri = *rit;
        if(ri < las) {
          return 0;
        }
        del(mxl, ri);
        add(las, ri);
        las = ri + 1;
      }
    } else {
      auto mx = *rp.rbegin();
      if(mx.first == 1) {
        return 1;
      }
      auto mxr = mx.second;
      rp.erase(mx);
      int las = mxr;
      tmp.clear();
      tmp.swap(r[mxr]);
      for(auto lit = tmp.rbegin(); lit != tmp.rend(); ++lit) {
        auto li = *lit;
        if(li > las) {
          return 0;
        }
        del(li, mxr);
        add(li, las);
        las = li - 1;
      }
    }
  }
}
int main() {
  int t;
  // scanf("%d", &t);
  cin >> t;
  while(t--) {
    // scanf("%d", &n);
    cin >> n;
    lp.clear();
    rp.clear();
    for(int i = 1; i <= n; i++) {
      l[i].clear();
      r[i].clear();
    }
    for(int i = 1, li, ri; i <= n; i++) {
      scanf("%d%d", &li, &ri);
      add(li, ri);
    }
    // printf("%d\n", work());
    cout << work() << '\n';
  }
  return 0;
}