#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>

using namespace std;
typedef long long LL;
const int maxn = 2e5 + 7, maxm = 4e5 + 7;

int h[maxn], e[maxm], ne[maxm], cnt;
int d[maxn], vis[maxn], jud[maxn];
LL s[maxn];

void add(int u, int v){
	e[cnt] = v;
	ne[cnt] = h[u];
	h[u] = cnt ++;
}
vector<int> loop;
int n;
void topsort(){
	memset(vis, 0, sizeof vis);
	queue<int> q;
	for (int i = 1; i <= n; i ++ ) if (d[i] == 1) q.push(i);
	
	while(!q.empty()){
		int u = q.front(); q.pop();
		vis[u] = 1;
		for (int i = h[u]; ~i; i = ne[i]){
			int v = e[i];
			d[v] --;
			if (d[v] == 1) q.push(v);
		}
	}
	
	for (int i = 1; i <= n; i ++ ) if (vis[i] == 0) loop.push_back(i), jud[i] = 1;
}

void dfs(int u, int f){
//	s[u] = 1;
	for (int i = h[u]; ~i; i = ne[i]){
		int v = e[i];
		if (jud[v] || v == f) continue;
		dfs(v, u);
		s[f] += s[v];
	}
}

int main (){
	
	int T;
	cin >> T;
	while (T -- ){
	
		cin >> n;
		for (int i = 0; i<= n; i ++ ) h[i] = -1, d[i] = 0, jud[i] = 0;
		cnt = 0;
		loop.clear();
		for (int i = 0;  i<= n; i ++ )s[i] = 1;
		for (int i = 0, u, v; i < n; i ++ ){
			scanf ("%d%d", &u, &v);
			add(u, v);
			add(v, u);
			d[u] ++, d[v] ++;
		}
		
		topsort();
		LL ans = 1ll * n * (n - 1);
		for (int i = 0; i < loop.size(); i ++ ){
			int u = loop[i];
			dfs(u, u);
			ans -= (s[u] * (s[u] - 1) / 2ll);
		}
		printf ("%lld\n", ans);	
		
	}
}
 			       	 		   		  					  	