#include<bits/stdc++.h>
using namespace std;
const int N = 1000010;

void solve()
{
    int n;
    cin >> n;
    vector<pair<int, int>> d(n + 1);
    for (int i = 1; i <= n;i++)
        cin >> d[i].first >> d[i].second;
    d[0].first = 0;
    d[0].second = 0;
    vector<int> fa(n + 1);
    for (int i = 0;i<=n;i++)
        fa[i] = i;
    auto find = [&](auto self, int u)
    {
        if(u == fa[u])
            return u;
        return fa[u] = self(self, fa[u]);
    };

    for (int i = 0; i < n;i++)
    {
        int u = d[i].first;
        int v = d[i + 1].second;
        int fu = find(find, u);
        int fv = find(find, v);
        
        if(fu == fv)
        {
            cout << 0 << endl;
            return;
        }
        fa[fu] = fv;
    }
    cout << 1 << endl;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int t;
    cin >> t;
    while(t--)
        solve();
    return 0;
}