#include<bits/stdc++.h>
using namespace  std ;
typedef long long LL ;
typedef pair<int,int> PII ;
#define endl '\n';
const int N = 1e6 + 100 ;
const int M=1e5+100;
const int mod = 1e9+7;

int n , m , k ;
int e[N];
void AC(){
    cin >> n ;
    for (int i = 1 ; i <= n ; i++ ) {
        e[i] = 0 ;
    }
    for ( int i = 1 ; i <= n ; i ++ ) {
        int u , v ; cin >> u >> v ;
        e[u] ++ ; e[v] ++ ;
    }
    bool fg = true ;
    for ( int i = 1 ; i <= n ; i++ ) {
        if ( e[i] & 1 ) {
            fg = false ;
            break;
        }
    }
    cout << fg << '\n';
    return;
}



int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int tt = 1 ;
    cin >> tt ;
    while( tt-- ) {
        AC();
    }
}

//  1  2  3 4 5 6 7 ....n