#include<bits/stdc++.h>
using namespace std;
const int N=1000010;
int s[N];
int height[N];
int a[N],b[N];
void init_set(int num)
{
    for(int i=1;i<=1+num;i++)
    {
        s[i]=i;
        height[i]=0;
    }
}
int find_set(int x)
{
    int r=x;
    while(s[r]!=r)r=s[r];
    int i=x,j;
    while(i!=r)
    {
        j=s[i];
        s[i]=r;
        i=j;
    }
    return r;
}
void union_set(int x,int y)
{
    x=find_set(x);
    y=find_set(y);
    if(height[x]==height[y])
    {
        height[x]+=1;
        s[y]=x;
    }
    else
    {
        if(height[x]<height[y])s[x]=y;
        else s[y]=x;
    }
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        int n;
        scanf("%d",&n);
        init_set(n);
        int flag=1;
        for(int i=1;i<=n;i++)
        {
            scanf("%d %d",&a[i],&b[i]);
        }
        for(int i=1;i<=n;i++)
        {
            if(s[a[i]]!=s[1+b[i]])union_set(a[i],1+b[i]);
            else
            {
                flag=0;
                break;
            }
        }
        printf("%d\n",flag);
    }
    return 0;
}