#include <iostream>
#include <vector>
#include <bitset>
using namespace std;

const int MAXN = 1000000; // Maximum value of n
const int WORD_SIZE = 64; // Size of word for bitset optimization

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<vector<int>> intervals(n);
        for (int i = 0; i < n; ++i) {
            int l, r;
            cin >> l >> r;
            // Store the indices of columns where M[i][j] = 1
            intervals[i] = {l - 1, r - 1};
        }

        // Initialize the matrix M as a vector of bitsets
        int size = (n + WORD_SIZE - 1) / WORD_SIZE;
        vector<vector<uint64_t>> M(n, vector<uint64_t>(size, 0));

        // Build the matrix M
        for (int i = 0; i < n; ++i) {
            int l = intervals[i][0];
            int r = intervals[i][1];
            for (int j = l; j <= r; ++j) {
                M[i][j / WORD_SIZE] |= (uint64_t(1) << (j % WORD_SIZE));
            }
        }

        // Gaussian elimination modulo 2
        bool possible = true;
        int rank = 0;
        for (int col = 0; col < n; ++col) {
            int pivot = -1;
            for (int row = rank; row < n; ++row) {
                if ((M[row][col / WORD_SIZE] >> (col % WORD_SIZE)) & 1) {
                    pivot = row;
                    break;
                }
            }
            if (pivot == -1) {
                possible = false;
                break;
            }
            swap(M[rank], M[pivot]);
            for (int row = 0; row < n; ++row) {
                if (row != rank && ((M[row][col / WORD_SIZE] >> (col % WORD_SIZE)) & 1)) {
                    for (int k = 0; k < size; ++k) {
                        M[row][k] ^= M[rank][k];
                    }
                }
            }
            ++rank;
        }

        cout << (possible ? 1 : 0) << '\n';
    }
    return 0;
}

answer.code: In function ‘int main()’:
answer.code:28:23: error: ‘uint64_t’ was not declared in this scope
   28 |         vector<vector<uint64_t>> M(n, vector<uint64_t>(size, 0));
      |                       ^~~~~~~~
answer.code:4:1: note: ‘uint64_t’ is defined in header ‘<cstdint>’; did you forget to ‘#include <cstdint>’?
    3 | #include <bitset>
  +++ |+#include <cstdint>
    4 | using namespace std;
answer.code:28:23: error: template argument 1 is invalid
   28 |         vector<vector<uint64_t>> M(n, vector<uint64_t>(size, 0));
      |                       ^~~~~~~~
answer.code:28:23: error: template argument 2 is invalid
answer.code:28:31: error: template argument 1 is invalid
   28 |         vector<vector<uint64_t>> M(n, vector<uint64_t>(size, 0));
      |                               ^~
answer.code:28:31: error: template argument 2 is invalid
answer.code:28:54: error: template argument 2 is invalid
   28 |         vector<vector<uint64_t>> M(n, vector<uint64_t>(size, 0));
      |                                                      ^
answer.code:28:64: error: expression list treated as compound expression in initializer [-fpermissive]
   28 |         vector<vector<uint64_t>> M(n, vector<uint64_t>(size, 0));
      |                                                                ^
answer.code:35:18: error: invalid types ‘int[int]’ for array subscript
   35 |                 M[i][j / WORD_SIZE] |= (uint64_t(1) << (j % WORD_SIZE));
      |                  ^
answer.code:45:23: error: invalid types ‘int[int]’ for array subscript
   45 |                 if ((M[row][col / WORD_SIZE] >> (col % WORD_SIZE)) & 1) {
      |                       ^
answer.code:54:19: error: invalid types ‘int[int]’ for array subscript
   54 |             swap(M[rank], M[pivot]);
      |                   ^
answer.code:54:28: error: invalid types ‘int[int]’ for array subscript
   54 |             swap(M[rank], M[pivot]);
      |                            ^
answer.code:56:39: error: invalid types ‘int[int]’ for array subscript
   56 |                 if (row != rank && ((M[row][col / WORD_SIZE] >> (col % WORD_SIZE)) & 1)) {
      |                                       ^
answer.code:58:26: error: invalid types ‘int[int]’ for array subscript
   58 |                         M[row][k] ^= M[rank][k];
      |                          ^
answer.code:58:39: error: invalid types ‘int[int]’ for array subscript
   58 |                         M[row][k] ^= M[rank][k];
      |                                       ^