 #include<bits/stdc++.h>
using  namespace std;

#define  ll                       long long
#define  pb                       push_back
#define  lb                       lower_bound
#define  ub                       upper_bound
#define  fr                       first
#define  sc                       second
#define  memset( a, b )           memset( a, b , sizeof(a) )
#define  mod                        1000000007
#define  rep( i , n )            for( i=0 ; i<n; i++ )
#define  INF                      1000000000000000000
#define FAST                     ios_base::sync_with_stdio (false), cin.tie(nullptr );
#define  N                        200003

  ll t ,d , ct  , q, ans ,l ,m , r ,n , mx, mn , i, j, k ,x , y , z , s  ;

  char ch;           string ss = "" ,  str = "" ;
 
  map<ll,ll>mp   ;     set< ll >st ;  

  ll a[N] ,  b[N] ;     
   

     /*  -------------------------------Main Code------------------------------- */      


vector<ll>v[N] , cont  ;   
bool vis[N] ;
bool rec[N] ;


void dfs(ll node , ll p = -1  )
{ 
      if(ct) return ;
       cont.pb(node) ;
    
vis[node]  = 1 ;

rec[node] = 1 ;

for(auto h : v[node])
{  if(ct) return ;
  if(h == p ) continue ; 
  if(rec[h])
    {    ct = 1 ;
             k = cont.size() - 1 ;

        for( j=0 ;j<cont.size() ;j++ )
             if(cont[j] == h )
              break ;

        return ;

    }
 
 if(ct) {return ; }

 if(!vis[h]) dfs(h , node) ;
}

cont.pop_back() ;
rec[node] =  0 ;

}


ll subtree(ll node , ll p = -1)
{
   vis[node] = 1 ;

 ll sz = 1 ;

for(auto h : v[node] )
{      if(p == h) continue ;
      if(st.count(h)) continue ;
    sz += subtree(h ,node) ;

}

return sz ;

}


int main(){       FAST             


 cin>>t ; while( t-- ) {

      s = k = d = l  = mx =m = mn = r= q =i=j = z= x= y =ct =ans = 0;

cont.clear() ;

cin >> n  ; 
for(i=1 ; i<=n ; i++) v[i].clear() , vis[i] = 0 , rec[i] = 0 ;

rep(i , n) cin >> x >> y , v[x].pb(y) , v[y].pb(x) ;

dfs(1 , -1) ;
for(i=1 ; i<=n ; i++) vis[i] = 0 ;

vector<ll>vec ;
ll tot = 0 ;
    
st.clear() ;

for(i = j ; i<=k ; i++)
 st.insert(cont[i]) ;

 for(auto h : st){

     ll sz = subtree(h , -1) ;   
tot += sz ;
vec.pb(sz) ;

}



for(auto h : vec)
{ 
  ans += h*(h-1)/2 ;
  ans += h*(tot -h) ;

}



cout << ans <<"\n" ;




}
return 0;
}



