#include <algorithm>
#include <iostream>
#include <list>
#include <vector>

using namespace std;

typedef pair<int, bool> pib;
typedef pair<int, int> pii;
typedef pair<int64_t, int64_t> pll;


list<int>* g;
int dp[200000];
bool visited[200000];
bool is_cycle[200000];
vector<int> cycle;

pib k;

bool search_cycle(int u, int p) {
	visited[u] = true;

	for (auto v : g[u]) {
		if (v == p) continue;
		if (visited[v]) {
			is_cycle[u] = true;
			cycle.push_back(u);
			k.first = v;
			k.second = true;
			return true;
		}
		else if (search_cycle(v, u)) {
			if (k.second) {
				is_cycle[u] = true;
				cycle.push_back(u);

				if (k.first == u) {
					k.second = false;
				}
			}
			return true;
		}
	}

	return false;
}

void dfs(int u, int p, int root) {
	visited[u] = true;
	if (u != root) ++dp[root];
	for (int v : g[u]) {
		if (v == p || visited[v] || is_cycle[v]) continue;
		dfs(v, u, root);
	}
}

void solve() {
	cycle.clear();
	int n; cin >> n;
	g = new list<int>[n];

	k = pib(0, false);

	for (int i = 0; i < n; ++i) {
		int u, v;
		cin >> u >> v;
		--u, --v;

		g[u].push_back(v);
		g[v].push_back(u);
		dp[i] = 0;
		visited[i] = false;
		is_cycle[i] = false;
	}

	search_cycle(0, 0);

	for (int i = 0; i < n; ++i)
		visited[i] = false;

	for (auto i : cycle) {
		dfs(i, i, i);
	}

	int64_t result = 0;
	int64_t t = n;
	for (auto i : cycle) {
		t -= dp[i];
		result += 2ll * t * dp[i] - dp[i] + (int64_t)dp[i] * ((int64_t)dp[i] - 1ll) / 2ll;
	}

	result += t * (t - 1);

	cout << result << endl;
}


int main() {
	ios::sync_with_stdio(false);
	int t; cin >> t;
	while (t--) solve();
}