#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define uint unsigned
#define mems(a, x) memset((a), (x), sizeof(a))

using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;

const int maxn = 100100;

int n, fa[maxn];
uint ans;
vector<int> G1[maxn], G2[maxn], G3[maxn];

int find(int x) {
	return fa[x] == x ? x : fa[x] = find(fa[x]);
}

int sz[maxn], son[maxn], dep[maxn], top[maxn];
int dfn[maxn], st[maxn], tim, ed[maxn], rnk[maxn];

int dfs(int u, int f, int d) {
	fa[u] = f;
	sz[u] = 1;
	dep[u] = d;
	int mx = -1;
	for (int v : G2[u]) {
		sz[u] += dfs(v, u, d + 1);
		if (sz[v] > mx) {
			son[u] = v;
			mx = sz[v];
		}
	}
	return sz[u];
}

void dfs2(int u, int tp) {
	top[u] = tp;
	dfn[u] = ++tim;
	if (!son[u]) {
		return;
	}
	dfs2(son[u], tp);
	for (int v : G2[u]) {
		if (!dfn[v]) {
			dfs2(v, v);
		}
	}
}

inline int qlca(int x, int y) {
	while (top[x] != top[y]) {
		if (dep[top[x]] < dep[top[y]]) {
			swap(x, y);
		}
		x = fa[top[x]];
	}
	if (dep[x] > dep[y]) {
		swap(x, y);
	}
	return x;
}

int so[maxn];

int dfs(int u) {
	st[u] = ++tim;
	rnk[tim] = u;
	int s = 1, mx = -1;
	for (int v : G1[u]) {
		int t = dfs(v);
		s += t;
		if (t > mx) {
			mx = t;
			so[u] = v;
		}
	}
	ed[u] = tim;
	return s;
}

struct node {
	uint sa, sb, sab;
};

inline node operator + (const node &a, const node &b) {
	node res;
	res.sa = a.sa + b.sa;
	res.sb = a.sb + b.sb;
	res.sab = a.sab + b.sab;
	return res;
}

namespace SGT {
	node a[maxn << 2];
	uint tag[maxn << 2];
	
	inline void pushup(int x) {
		a[x] = a[x << 1] + a[x << 1 | 1];
	}
	
	inline void pushtag(int x, int l, int r, uint y) {
		a[x].sa += y * (r - l + 1);
		a[x].sab += y * a[x].sb;
		tag[x] += y;
	}
	
	inline void pushdown(int x, int l, int r) {
		int mid = (l + r) >> 1;
		if (tag[x]) {
			pushtag(x << 1, l, mid, tag[x]);
			pushtag(x << 1 | 1, mid + 1, r, tag[x]);
			tag[x] = 0;
		}
	}
	
	void build(int rt, int l, int r) {
		tag[rt] = a[rt].sa = a[rt].sb = a[rt].sab = 0;
		if (l == r) {
			return;
		}
		int mid = (l + r) >> 1;
		build(rt << 1, l, mid);
		build(rt << 1 | 1, mid + 1, r);
	}
	
	void update(int rt, int l, int r, int ql, int qr, uint x) {
		if (ql <= l && r <= qr) {
			pushtag(rt, l, r, x);
			return;
		}
		pushdown(rt, l, r);
		int mid = (l + r) >> 1;
		if (ql <= mid) {
			update(rt << 1, l, mid, ql, qr, x);
		}
		if (qr > mid) {
			update(rt << 1 | 1, mid + 1, r, ql, qr, x);
		}
		pushup(rt);
	}
	
	void modify(int rt, int l, int r, int x, uint y) {
		if (l == r) {
			a[rt].sb = y;
			a[rt].sab = a[rt].sa * y;
			return;
		}
		pushdown(rt, l, r);
		int mid = (l + r) >> 1;
		(x <= mid) ? modify(rt << 1, l, mid, x, y) : modify(rt << 1 | 1, mid + 1, r, x, y);
		pushup(rt);
	}
	
	uint query(int rt, int l, int r, int ql, int qr) {
		if (ql <= l && r <= qr) {
			return a[rt].sab;
		}
		pushdown(rt, l, r);
		int mid = (l + r) >> 1;
		uint res = 0;
		if (ql <= mid) {
			res += query(rt << 1, l, mid, ql, qr);
		}
		if (qr > mid) {
			res += query(rt << 1 | 1, mid + 1, r, ql, qr);
		}
		return res;
	}
}

inline void upd(int x, uint y) {
	// printf("upd %d %u\n", x, y);
	while (x) {
		// printf("upd %d %d\n", dfn[top[x]], dfn[x]);
		SGT::update(1, 1, n, dfn[top[x]], dfn[x], y);
		x = fa[top[x]];
	}
}

inline uint qry(int x) {
	uint res = 0;
	while (x) {
		res += SGT::query(1, 1, n, dfn[top[x]], dfn[x]);
		x = fa[top[x]];
	}
	return res;
}

set<pii> S;
int stk[maxn], tp;
bool vis[maxn];

inline void add(int x) {
	// printf("add %d\n", x);
	if (!vis[x]) {
		vis[x] = 1;
		stk[++tp] = x;
		SGT::modify(1, 1, n, dfn[x], x);
	}
}

inline void clear() {
	// puts("clear");
	for (int i = 1; i <= tp; ++i) {
		int x = stk[i];
		vis[x] = 0;
		SGT::modify(1, 1, n, dfn[x], 0);
	}
	tp = 0;
}

void dfs3(int u) {
	if (!so[u]) {
		ans += 1U * u * u;
		S.emplace(dfn[u], u);
		add(u);
		upd(u, 1);
		return;
	}
	for (int v : G1[u]) {
		if (v == so[u]) {
			continue;
		}
		dfs3(v);
		S.clear();
		clear();
		for (int i = st[v]; i <= ed[v]; ++i) {
			int w = rnk[i];
			upd(w, -1);
		}
	}
	dfs3(so[u]);
	for (int v : G1[u]) {
		if (v == so[u]) {
			continue;
		}
		for (int i = st[v]; i <= ed[v]; ++i) {
			int w = rnk[i];
			S.emplace(dfn[w], w);
			auto it = S.find(mkp(dfn[w], w));
			if (it != S.begin()) {
				auto jt = prev(it);
				int x = qlca(jt->scd, w);
				add(x);
			}
			if (next(it) != S.end()) {
				auto jt = next(it);
				int x = qlca(jt->scd, w);
				add(x);
			}
			upd(w, 1);
			add(w);
		}
	}
	S.emplace(dfn[u], u);
	auto it = S.find(mkp(dfn[u], u));
	if (it != S.begin()) {
		auto jt = prev(it);
		int x = qlca(jt->scd, u);
		add(x);
	}
	if (next(it) != S.end()) {
		auto jt = next(it);
		int x = qlca(jt->scd, u);
		add(x);
	}
	upd(u, 1);
	add(u);
	ans += qry(u) * u;
	// printf("u: %d %u\n", u, qry(u));
}

void solve() {
	scanf("%d", &n);
	tim = 0;
	for (int i = 1; i <= n; ++i) {
		vector<int>().swap(G1[i]);
		vector<int>().swap(G2[i]);
		vector<int>().swap(G3[i]);
		fa[i] = i;
		son[i] = dep[i] = top[i] = dfn[i] = so[i] = 0;
	}
	for (int i = 1, u, v; i < n; ++i) {
		scanf("%d%d", &u, &v);
		G3[u].pb(v);
		G3[v].pb(u);
	}
	for (int i = 1; i <= n; ++i) {
		fa[i] = i;
	}
	for (int i = n; i; --i) {
		for (int j : G3[i]) {
			if (i > j) {
				continue;
			}
			j = find(j);
			G1[i].pb(j);
			fa[j] = i;
		}
	}
	for (int i = 1; i <= n; ++i) {
		fa[i] = i;
	}
	for (int i = 1; i <= n; ++i) {
		for (int j : G3[i]) {
			if (i < j) {
				continue;
			}
			j = find(j);
			G2[i].pb(j);
			fa[j] = i;
		}
	}
	dfs(n, 0, 1);
	dfs2(n, n);
	tim = 0;
	ans = 0;
	dfs(1);
	SGT::build(1, 1, n);
	dfs3(1);
	clear();
	printf("%u\n", ans);
}

int main() {
	int T = 1;
	scanf("%d", &T);
	while (T--) {
		solve();
	}
	return 0;
}