#include<iostream>
#include<vector>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<queue>
#include<cmath>
#include<set>
using namespace std;
int e[40000][2];int head[10000];int nume=0;
int vis[40000];
int n;
void adde(int i,int j)
{
    e[nume][0]=j;e[nume][1]=head[i];head[i]=nume++;
    e[nume][0]=i;e[nume][1]=head[j];head[j]=nume++;
}
 int vvis[200];
void dfs(int cur)
{
    for(int j=head[cur];j!=-1;j=e[j][1])
    {
        if(vis[j])continue;
        int to=e[j][0];
        if(!vvis[to])
        {
            vvis[to]=1;
            dfs(to);
        }
    }
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
      scanf("%d",&n);
      for(int i=0;i<10000;i++)
      {
          head[i]=-1;
           vis[i]=0;
      }
      nume=0;
      int xx,yy;
      for(int i=0;i<n+1;i++)
      {
        scanf("%d%d",&xx,&yy);
        adde(xx,yy);
      }
      int ans=0;
      for(int k=1;k<=n;k++)
              vvis[k]=0;
              vvis[1]=1;
      dfs(1);
       int mark=1;
           for(int k=1;k<=n;k++)
             if(!vvis[k])
                {
                    mark=0;break;
                }
            if(!mark)
            {
                printf("0\n");continue;
            }
      for(int i=0;i<n+1+n+1;i=i+2)
      {
          vis[i+1]=vis[i]=1;

          for(int k=1;k<=n;k++)
              vvis[k]=0;
            vvis[1]=1;
          dfs(1);
          int mark=1;
           for(int k=1;k<=n;k++)
             if(!vvis[k])
                {
                    mark=0;break;
                }
         if(mark)
         {
             ans++;

         }
         else
         {
             vis[i+1]=vis[i]=0;
             continue;
         }



         for(int j=i+2;j<n+1+n+1;j=j+2)
         {
             vis[j+1]=vis[j]=1;

          for(int k=1;k<=n;k++)
              vvis[k]=0;
            vvis[1]=1;
          dfs(1);
          int mark=1;
           for(int k=1;k<=n;k++)
             if(!vvis[k])
                {
                    mark=0;break;
                }
         if(mark)
         {
             ans++;
              vis[j+1]=vis[j]=0;
         }
         else
         {
             vis[j+1]=vis[j]=0;
         }
         }

          vis[i+1]=vis[i]=0;
      }
      printf("%d\n",ans);

    }
    return 0;
}