#include <bits/stdc++.h>

using namespace std;

const int MX = 5000;

int ans[MX], n;
vector<pair<int, int>> G[2 * MX];
set<int> C[2 * MX];

void dfs(int v, int p = -1) {
	for (auto& e : G[v]) {
		if (e.first == p) continue;
		
		dfs(e.first, v);
		
		auto& D = C[e.first];
		if (D.empty()) continue;
		
		ans[e.second] += n - *D.begin();
		
		if (D.size() > C[v].size()) swap(C[v], D);
		for (int x : D) {
			if (C[v].count(x) == 1) C[v].erase(x);
			else C[v].insert(x);
		}
	}
}

int p[2 * MX];

int dsu_get(int v) {
	if (p[v] != v) p[v] = dsu_get(p[v]);
	return p[v];
}

bool dsu_merge(int u, int v) {
	u = dsu_get(u);
	v = dsu_get(v);
	p[u] = v;
	return u != v;
}

int u[MX], v[MX];

int main() {
	int T;
	ignore = scanf("%d", &T);
	while (T--) {
		ignore = scanf("%d", &n);
		for (int i = 0; i < n; i++) {
			ignore = scanf("%d %d", u + i, v + i);
			u[i]--;
			v[i]--;
			ans[i] = 0;
		}
		
		for (int l = 0; l < n; l++) {
			for (int i = 0; i < 2 * MX; i++) {
				p[i] = i;
				G[i].clear();
				C[i].clear();
			}
			
			for (int r = l; r < n; r++) {
				if (dsu_merge(u[r], v[r])) {
					G[u[r]].emplace_back(v[r], r);
					G[v[r]].emplace_back(u[r], r);
				}
				else {
					C[u[r]].insert(r);
					C[v[r]].insert(r);
					
					ans[r] += n - r;
				}
			}
			
			for (int v = 0; v < 2 * MX; v++) if (p[v] == v) dfs(v);
		}
	
		for (int i = 0; i < n; i++) printf("%d ", ans[i]);
		printf("\n");
	}
	
	return 0;
}