#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define mt make_tuple
#define pii pair<int, int>
#define pll pair<long long,long long>
#define vl vector<long long>
#define vll vector<pll>
#define vi vector<int>
#define vii vector<pii>
#define sws ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define endl '\n'
#define tcase int tt; cin>>tt; while(tt--)
#define tcase2 int tt; cin>>tt; for(int qq=1;qq<=tt;qq++)
using namespace std;
typedef long long int ll;
typedef  unsigned long long int ull;
typedef long double ld;
const int MAXN = 1000002;
const int MOD2 = 998244353;
const int MOD = 1000000007; 
const int INF = 1e8;
const ld EPS = 1e-7;
// Extra
#define forn(i, n) for(int i = 0; i < (int)n; i++)
#define forne(i, a, b) for(int i = a; i <= b; i++)
#define all(x) x.begin(), x.end()
#define trav(a, x) for(auto& a : x)
#define fill(x,y) memset(x,y,sizeof(x))
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
ll mul(ll x, ll y)
{
    return (x * 1ll * y) % MOD;
}
 
ll fastpow(ll x, ll y)
{
    ll z = 1;
    while(y)
    {
        if(y & 1) z = mul(z, x);
        x = mul(x, x);
        y >>= 1;
    }
    return z;
}
ll modinv(ll n,ll p)
{
	return fastpow(n,p-2) ;
}
struct Comp {
  bool operator()(const std::pair<int, int> &a, const std::pair<int, int> &b) {
    if (a.first != b.first) {
      return a.first > b.first;
    }
    return a.second >b.second;
  }
};
vector<ll>adj[200001],adj2[200001];
ll color[200001];
ll par[200001] ;
ll k=0 ;
bool vis[200001];
vector<ll>tr;
set<ll>cycle ;
void dfs(ll x, ll p )
{
	if(color[x]==2)
	return  ;
	ll cur=p ;
	if(color[x]==1)
	{
		cycle.insert(x) ;
		while(cur!=x)
		{
			cycle.insert(cur) ;
			cur=par[cur] ; 
		}
		return ;
	}
	par[x]=p;
	color[x]=1 ;
	for(auto u:adj[x])
	{
		if(u!=p)
		{
			dfs(u,x) ;
		}
	}
	color[x]=2 ;
	
}
void dfs2(ll x)
{
	if(vis[x])
	return  ;
	vis[x]=true ;
	k++;
	for(auto u:adj2[x])
	{
		dfs2(u) ;
	}
}
int main(int argc, char** argv)
{   sws ;
  cout<<setprecision(10);
 // ll x=1 ;
   tcase
   {
   ll n ;
   cin>>n ;
   ll u[n],v[n] ;
   forn(i,n)
   {
   	adj[i].clear() ;
   	adj2[i].clear() ;
   	vis[i]= 0;
   	color[i]=0 ;
   	par[i]=-1 ;
   	
   }
   cycle.clear() ;
   tr.clear();
   forn(i,n)
   { 
   	cin>>u[i]>>v[i];
   	u[i]--;v[i]-- ;
   	adj[v[i]].pb(u[i]) ;
   	adj[u[i]].pb(v[i]) ;
   	
   	
   }
   dfs(0,-1) ;
   vector<ll>cyc ;
  // sort(cycle.begin(),cycle.end()) ;
   for(auto x:cycle)
   {//cout<<x<<" " ;
   cyc.pb(x) ;
   }
 //  vector<ll>cyc;
   forn(i,n)
   {
   	if(binary_search(cyc.begin(),cyc.end(),u[i])&&binary_search(cyc.begin(),cyc.end(),v[i]))
   	continue ;
   	else
   	{
   		adj2[u[i]].pb(v[i]) ;
   		adj2[v[i]].pb(u[i]) ;
	   }
   }
   ll s=0 ,ans=0;
   forn(i,n)
   {
   	if(!vis[i])
   	{  k=0 ;
   		dfs2(i);
   		s+=k ;
   		tr.pb(k) ;
	   }
   }
   
   forn(i,tr.size())
   { //cout<<tr[i]<<" ";
   	ans+=(tr[i]*(tr[i]-1))/2 ;
   	ans+=(tr[i])*(s-tr[i]) ;
   }
   cout<<ans<<"\n" ;
   
   }
return 0 ;
}