#include "bits/stdc++.h"
#define  int            long long
#define  fi             first
#define  se             second
#define  endl           '\n'
#define  mp             make_pair
#define  pb             push_back
#define  MOD            1000000007
#define  INF            0x3f3f3f3f
#define  vi             vector<int>
#define  pii            pair<int,int>
#define  mii            map<int,int>
#define  eb             emplace_back
#define  float          long double
#define  all(v)         v.begin(), v.end()
#define  f(i,n)         for(int i=0;i<n;++i)
#define  test           int T; cin>>T; while(T--)
#define  rep(i,s,e)     for(int i=s;i<e;++i)
#define  repd(i,e,s)    for(int i=e;i>=s;--i)
#define  reset(v)       memset((v), 0, sizeof(v))
#define  deb(x)         cerr << #x << " is " << x << endl;
#define  fast_io        ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
using namespace std;
const int mxn = 2e5 + 1;
vi adj[mxn], col(mxn), par(mxn), tmp;
unordered_map<int, bool> cy;
int n, cnt = 1;
void dfs(int u, int p) {
	if(col[u] == 2) return;
	if(col[u] == 1) {
		int cur = p;
		cy[u] = 1; cy[cur] = 1;
		while(cur != u) {
			cur = par[cur];
			cy[cur] = 1;
		}
		return;
	}
	par[u] = p;
	col[u] = 1;
	for(auto v: adj[u]) {
		if(v == par[u]) continue;
		dfs(v, u);
	}
	col[u] = 2;
}
void dfs1(int u) {
	cnt++; col[u] = 1;
	for(auto it: adj[u]) if(!col[it]) dfs1(it);
}
signed main() {
	fast_io
	test {
		int u, v, ans = 0;
		cy.clear(); tmp.clear();
		f(i, n + 1) {col[i] = 0; par[i] = 0; adj[i].clear();}
		cin >> n;
		f(i, n) {
			cin >> u >> v;
			adj[u].eb(v);
			adj[v].eb(u);
		}
		ans = (n * (n - 1)) / 2ll;
		dfs(1, 0);
		f(i, n + 1) col[i] = 0;
		for(auto it: cy) {
			cnt = 1;
			col[it.fi] = 1;
			for(auto ut: adj[it.fi]) if(!cy.count(ut)) dfs1(ut);
			tmp.eb(cnt);
		}
		int x = 0;
		rep(i, 0, tmp.size()) {
			x += tmp[i];
			ans += tmp[i] * (n - x);
		}
		cout << ans << endl;
	}
	return 0;
}