#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define mp make_pair
#define ll long long
#define FOR(i,a,b) for(int i=(int)(a); i<=(int)(b); i++)
#define FORD(i,a,b) for(int i=(int)(a);i>=(int)(b);i--)
typedef pair<int,int> pi;
typedef pair<ll,ll> pl;



void solve(){
	int n,u,v;
    cin>>n;
    vector <set<int>> adj(n+1);
    ll value[n+1],ans=0;
    FOR(i,1,n) value[i]=1;
    FOR(i,1,n){
    	cin>>u>>v;
    	adj[u].insert(v);
    	adj[v].insert(u);
	}
	queue <int> leaf;
	FOR(i,1,n){
		if(adj[i].size()==1){
			leaf.push(i);
		}
	}
	while(!leaf.empty()){
		int z=leaf.front();
		leaf.pop();
		int par=*adj[z].begin();
		value[par]+=value[z];
		value[z]=0;
		adj[z].clear();
		adj[par].erase(z);
		if(adj[par].size()==1){
			leaf.push(par);
		}
	}
	FOR(i,1,n){
		ans+= value[i]*(value[i]-1)/2;
		ans+= value[i]*(n-value[i]);
	}
	cout<<ans<<endl;
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int t=1;
	cin>>t;
	while(t--){
		solve();
	}
}