#include "bits/stdc++.h"
using namespace std;
#define all(x) x.begin(),x.end()
#define pb push_back
#define ff first
#define ss second
#define fast ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define ar array
#define int long long 
#define F(i,a,b) for(i=a;i<b;++i)
#define RF(i,b,a) for(i=b;i>=a;--i) 
#define NL cout<<"\n";
#define INF LONG_LONG_MAX

typedef long long ll;
typedef long double ld;
const ll mod=1e9+7;
bool comp(ll a,ll b)
{
	return a<b;
}
ll fpow(ll a, ll b) {

	ll res=1;
	while(b) {
		if(b&1)
			res=(res*a);
		a=(a*a);
		b>>=1;
	}
	return res;
}

ll minm(ll a,ll b){
	if(a<b) return a;
	return b;
}

ll maxm(ll a,ll b){
	if(a>b){ return a;}
	else return b;
}

int PHI(int k){
	// This is Euler's Totient Function.
	//This function returns no. of coprime numbers to N in range [1,2,....,N]

	  int ans=k;
	  for(int i=2;i*i<=k;++i){
	  	if(k%i==0){
	  		ans-=ans/i;
	  		while(k%i==0){
	  			k/=i;
	  		}
	  	}
	  }
     if(k>1) ans-=ans/k;
     return ans;
 

}

const int N=2e5+5;

int n;
vector<int>adj[N];
vector<int>parent(N),color(N);
int cycle_start=-1,cycle_end=-1;

bool dfs(int u,int par){
   	color[u]=1;
   	
   	for(int x:adj[u]){
   		if(x==par){
   			continue;
   		}
   		
   		if(color[x]==0){
   			parent[x]=u;
   			if(dfs(x,u))
   			return true;
   		}
   		
   		else if(color[x]==1){
   			cycle_start=x;
   			cycle_end=u;
   			return true;
   		}
   		
   	}
   	color[u]=2;
   	return false;
   	
}

vector<int> find_cycle(){
	vector<int>cycle;
	cycle_end=-1;
	cycle_start=-1;
	
	
	for(int i=1;i<=n;++i){
		if(color[i]==0 && dfs(i,parent[i])){
			break;
		}
	}
	
	if(cycle_start==-1){
		return {};
	}
	
	vector<int>ans;
	ans.pb(cycle_start);
	
	for(int i=cycle_end;i!=cycle_start;i=parent[i]){
	  	ans.pb(i);
	}
	ans.pb(cycle_start);
	
	return ans;
	
}


void solve(){
  int i;
  cin >> n;
  
  for(i=1;i<=n;++i){
  	adj[i].clear();
  	color[i]=0;
  	parent[i]=-1;
  }
  
  
  for(i=0;i<n;++i){
  	int x,y;
  	cin >> x >> y;
  	adj[x].pb(y);
  	adj[y].pb(x);
  	
  }
  
  vector<int> cycle=find_cycle();
  
  int k=(int)cycle.size()-1;
  
  //int ans=0,ans2=0,ans1=(k*(k-1));
  
  int ans=0;
  
  vector<bool>vis(n+1,false);
 
   cycle.pop_back(); 
    for(auto x:cycle){
     	vis[x]=1;
     }
  
  //queue<int>q;
  for(int i:cycle){
  		int cnt=0;
  //	 if(!vis[i]){
  	 	
  	 	queue<int>q;
  	 	q.push(i);
  	 
  	 	vis[i]=1;
  	 	
  	 	while(!q.empty()){
  	 		++cnt;
  	 		int p=q.front(); q.pop();
  	 		for(auto node:adj[p]){
  	 			if(!vis[node]){
  	 				vis[node]=1;
  	 				q.push(node);
  	 			}
  	 		}
  	 	}
  	 	
  	     
  	     	
  	// }
  	 
  	 //  cout<<i<<" "<<cnt<<"\n";
  	 //     ++cnt;
  	 	ans+=(cnt*(cnt-1))/2;
  	 	ans+=(cnt*(n-cnt));
  	 
  	 
  }
  
  cout<<ans<<"\n";
 
}


signed main(void)     
{

	fast;

 //  #ifndef ONLINE_JUDGE
//	  freopen("input.txt","r",stdin);
//	  freopen("output.txt","w",stdout);
  //  #endif

	int _=1;
	cin>>_;
 
      for(int test_case=1;test_case<=_;++test_case){
         solve();
      }
   
	
}

