#include<iostream>
using namespace std;
#define MAX 105
int father[MAX],flag,sign[MAX];
void init();
bool ok();
int FindSet(int x)
{
    while(x!=father[x])
        x=father[x];
    return x;
}
void Union(int x,int y)
{
    x=FindSet(x);
    y=FindSet(y);
        father[x]=y;
}
struct node
{
    int a,b;
};
       int n=0;
int main()
{
  int T=0;
  cin>>T;
  while(T--)
  {
       int sum=0;
       node map[103];
       cin>>n;
       for(int i=0;i<=n;i++)
       {
           cin>>map[i].a>>map[i].b;
     }
     for(int i=0;i<=n;i++)
     {
         init();
         for(int j=0;j<=n;j++)
         {
             if(j==i)
              continue;
             Union(map[j].a,map[j].b);
        }
        if(ok()) sum++;
     }
     for(int i=0;i<=n;i++)
     {
         for(int j=i+1;j<=n;j++)
         {
             init();
             for(int k=0;k<=n;k++)
            {
             if(k==i||k==j)
              continue;
             Union(map[k].a,map[k].b);
           }
          if(ok()) sum++;
        }
     }
     cout<<sum<<endl;
  }    
    return 0;
}
void init()
{
    for(int i=1;i<=n;i++)
     father[i]=i;
}
bool ok()
{
    int sum=0;
    for(int i=1;i<=n;i++)
    {
        if(father[i]==i) sum++;
    }
    if(sum>1) return 0;
    return 1;
}