#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mod 1000000007
ll int maxm(ll int a,ll int b) {ll int c=a>b?a:b; return c;}
ll int minm(ll int a,ll int b) {ll int c=a>b?b:a; return c;}
vector<bool>vis(200001,false);
vector<vector<ll int>>adj(200001);
vector<ll int>dst(200001,0);
vector<ll int>par(200001,0),par1(200001,0);
ll int n,fst,lst;
set<ll int>sac;
ll int dd(int v)
{
    ll int ans=0;
    for(auto u:adj[v])
    {
        if(u!=par1[v])
        {   par1[u]=v;
            ans+=dd(u);
        }
    } return ans+1;
}
bool dfs(int node)
{
   vis[node]=true;
   for(auto v:adj[node])
   {
       if(v!=par[node])
       {
           if(!vis[v])
           {
               par[v]=node;
               dst[v]=dst[node]+1;
               if(dfs(v))
                return true;
           }
           else if(vis[v])
           {
               fst=v;
               lst=node;
               return true;
           }
       }
   }
   return false;
}
void solve(void)
{
    for(ll int i=1;i<=n;i++)
    {adj[i].clear();vis[i]=false;dst[i]=0;par[i]=0;par1[i]=0;}
    sac.clear();
    cin>>n;
    ll int a,b;
    ll int i,h=0;
     for(i=0;i<n;i++)
   {
    cin>>a>>b;
    adj[a].push_back(b);
    adj[b].push_back(a);
   }
   for(i=1;i<=n;i++)
   {
    if(!vis[i])
    { dst[i]=0;par[i]=0;
        if(dfs(i)){break;}
    }
   }
   for(int pp=lst;1;pp=par[pp])
    { sac.insert(pp);
     if(pp==fst) break;}

    sac.insert(lst);
   ll int ans=n*(n-1);
   for ( auto nn: sac)
   {
       ll int hlp=0;
       for(auto u:adj[nn])
       {
           if(sac.find(u)==sac.end())
           {   par1[u]=nn;
               hlp+=dd(u);
           }
       }
        hlp++;
        hlp=hlp*(hlp-1);
        hlp/=2;
        ans-=hlp;
    }
    cout<<ans<<endl;
}
int main()
{
    int t=1;
    cin>>t;
    while(t--)solve();
}
