#include <bits/stdc++.h>

using namespace std;

int main(){
	int t;
	cin >> t;

	while(t--){
		int n;
		cin >> n;
		vector<set<int>> v(n);

		for(int i = 0; i < n; ++i){
			int x, y;
			cin >> x >> y;
			--x;
			--y;
			v[x].insert(y);
			v[y].insert(x);
		}
		vector<int> val(n, 1);
		queue<int> leafs;

		for(int i = 0; i<n; ++i){
			if (v[i].size() == 1){
				leafs.push(i);
			}
		}

		while(!leafs.empty()){
			int a = leafs.front();
			leafs.pop();
			int b = *v[a].begin();
			val[b] += val[a];
			val[a] = 0;
			v[a].clear();
			v[b].erase(a);
			if(v[b].size() == 1){
				leafs.push(b);
			}
		}

		long long ans = 0;
		
		for(int i = 0; i < n; ++i){
			ans += val[i] * 1ll * (val[i]-1)/2;
			ans += val[i] * 1ll * (n - val[i]);
		}

		cout << ans << '\n';
	}

	return 0;
}
