#define _CRT_SECURE_NO_WARNINGS 
#include <iostream>
#include <algorithm>
#include <functional>
#include <utility>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <vector>
#include <string>
#include <queue>
#include <stack>
#include <map>
#include <set>
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
#define deg(x) cout << #x << '=' << x << endl
#define Close ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
#define mk(a, b) make_pair(a, b)
#define lowbit(x) (x & (-x))
#define inf 0x3f3f3f3f
#define lson p << 1
#define rson p << 1 | 1
template <typename T>
inline void read(T& x) {
	char ch = getchar();
	bool flag = false;  x = 0;
	while (!isdigit(ch)) flag |= (ch == '-'), ch = getchar();
	while (isdigit(ch)) x = x * 10 + ch - '0', ch = getchar();
	if (flag) x = -x;
}
const ll Mod = 1000000007;
const int N = 2e5 + 5, M = 4e5 + 5;
 
vector<int> v[N];
vector<int> d;
int st[N], in[N], top;
ll sz[N];
bool vis[N];
int ok = 0;
 
void dfs(int x, int pre) {
	if (ok) return;
	st[++top] = x, in[x] = 1;
	for (int y : v[x]) {
		if (y == pre) continue;
		if (in[y]) {
			int cnt = top;
			while (st[cnt] != y) {
				d.push_back(st[cnt]);
				vis[st[cnt]] = 1;
				cnt--;
			}
			d.push_back(y);
			vis[y] = 1;
			ok = 1;
			return;
		}
		else dfs(y, x);
	}
	in[st[top--]] = 0;
}
 
void dfs2(int x, int pre) {
	sz[x] = 1;
	for (int y : v[x]) {
		if (vis[y] || y == pre) continue;
		dfs2(y, x);
		sz[x] += sz[y];	
	}
}
 
int main()
{
	Close;
	int T, n;
	cin >> T;
	while (T--) {
		cin >> n;
		d.clear();
		top = 0;
 
		for (int i = 1; i <= n + 1; i++) {
			v[i].clear();
			in[i] = vis[i] = sz[i] = 0;
		}
 
		for (int i = 1; i <= n; i++) {
			int x, y;
			cin >> x >> y;
			v[x].push_back(y);
			v[y].push_back(x);
		}
 
		ok = 0;
		dfs(1, 1);
		for (auto it : d)
			dfs2(it, it);
		ll dsz = d.size();
		ll ans = dsz * (dsz - 1);
		ll res = 0;
		for (int y : d) {
			ll szy = sz[y] - 1;
			ans += szy + szy * (dsz - 1) * 2;
			ans += szy * (szy - 1) / 2;
			res += szy * (n - szy - dsz) * 2;
		}
 
		ans += res / 2;
		cout << ans << endl;
		//deg(ans);
	}
	return 0;
}