#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#include <deque>
#include <bitset>
#include <iterator>
#include <list>
#include <stack>
#include <map>
#include <set>
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <climits>
#include <iterator>
using namespace std;
 
typedef long long ll;
const ll mod=1e9+7;
const ll N=2e5+1;
const ll INF=1e10; 

vector<vector<int>> adj(N);
vector<bool> visited(N);
vector<int> parent(N),root(N);
pair<int,int> backedge;

void dfs(int cur){
	visited[cur]=true;
	for(int next:adj[cur]){
		if(!visited[next]){
			parent[next]=cur;
			dfs(next);
		}
		else if(parent[cur]!=next) backedge={cur,next};
	}
}

void solve(){
	map<int,int> subtree;
	int n;
	cin>>n;
	for(int i=0;i<n;i++){
		int u,v;
		cin>>u>>v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	dfs(1);
	//cout<<backedge.first<<' '<<backedge.second<<'\n';/*
	for(int i=0;i<adj[backedge.first].size();i++){
		if(adj[backedge.first][i]==backedge.second){
			adj[backedge.first][i]=adj[backedge.first].back();
			adj[backedge.first].pop_back();
			//cout<<"done";
			break;
		}
	}
	for(int i=0;i<adj[backedge.second].size();i++){
		if(adj[backedge.second][i]==backedge.first){
			adj[backedge.second][i]=adj[backedge.second].back();
			adj[backedge.second].pop_back();
			//cout<<"done";
			break;
		}
	}
	//cout<<"done";/*
	for(int i=1;i<=n;i++) parent[i]=-1,visited[i]=false;
	parent[backedge.first]=0;
	dfs(backedge.first);
	for(int i=1;i<=n;i++) visited[i]=false;
	queue<int> q;
	q.push(backedge.second);
	root[backedge.second]=backedge.second;
	visited[q.back()]=true;
	while(parent[q.back()]){
		//cout<<q.back()<<' ';
		visited[parent[q.back()]]=true;
		q.push(parent[q.back()]);
		root[q.back()]=q.back();
	}
	visited[backedge.first]=true;
	root[backedge.first]=backedge.first;
	ll c=q.size();
	while(!q.empty()){
		int t=q.front();
		q.pop();
		for(int i:adj[t]){
			if(!visited[i]){
				root[i]=root[t];
				subtree[root[i]]++;
				visited[i]=true;
				q.push(i);
			}
		}
	}
	//for(auto i:subtree) cout<<i.first<<' '<<i.second<<'\n';
	ll ans1=0,ans2=0,sum=0;
	for(auto i:subtree){
		ans1+=(ll)i.second*(i.second+1)/2;
		ans2+=i.second*sum;
		sum+=i.second;
	}
	ans1+=2*ans2+2*(c-1)*(n-c)+c*(c-1);
	cout<<ans1<<'\n';
	for(int i=1;i<=n;i++){
		adj[i].clear();
		visited[i]=false;
		parent[i]=0;
	}
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(NULL);
	int t;
	cin>>t;
	while(t--) solve();
} 