#include<bits/stdc++.h>
using namespace std;

typedef long long LL;
typedef pair<int, int> PII;
const int N = 2e5 + 100, M = 1e5 + 100;
const int inf = 0x3f3f3f3f;
const LL INF = 0x3f3f3f3f3f3f3f3f;
#define x first
#define y second
const int mod = 1e9 + 7;
#define gcd __gcd
const double eps = 1e-8;
const double PI = acos(-1.0);

LL res[N];
vector<int> e[N];
int siz[N], f[N][35];
int dep[N];
bool vis[N];

void dfs(int u, int fa, int d) {
	dep[u] = d;
	f[u][0] = fa;
	siz[u] = 1;
	for(int i = 1; i <= 30; i++) {
		f[u][i] = f[f[u][i - 1]][i - 1];
	}
	for(auto v : e[u]) {
		if(v == fa) continue;
		dfs(v, u, d + 1);
		siz[u] += siz[v];
	}
}

int get(int x, int d) {
	int now = x;
	for(int i = 30; i >= 0; i--) {
		// if(now == 3 && d == 2) cout << dep[f[x][i]] << endl;
		if(dep[f[x][i]] >= d) {
			x = f[x][i];
		}
	}
	// if(now == 3 && d == 2) cout << "namo " << x << endl;
	return x;
}

void solve() {
	int n;
	scanf("%d", &n);
	for(int i = 1; i <= n + 1; i++) {
		res[i] = 0;
		e[i].clear();
		vis[i] = false;
	}
	for(int i = 1; i < n; i++) {
		int u, v;
		scanf("%d%d", &u, &v);
		u++; v++;
		e[u].push_back(v);
		e[v].push_back(u);
	}
	dfs(1, 0, 1);

	for(auto v : e[1]) {
		res[1] += 1LL * siz[v] * (siz[v] - 1) / 2;
	}

	int cur = 2;
	while(f[cur][0] != 1) {
		cur = f[cur][0];
	}
	int sum = 0;
	for(auto d : e[1]) {
		if(d == cur) sum += siz[d] - siz[2];
		else sum += siz[d];
	}
	for(auto d : e[1]) {
		if(d == cur) res[2] += 1LL * (siz[d] - siz[2]) * (sum - (siz[d] - siz[2]));
		else res[2] += 1LL * siz[d] * (sum - siz[d]);
	}
	res[2] /= 2;
	res[2] += sum;
	siz[1] -= siz[cur];

	cur = 2;
	while(!vis[cur]) {
		vis[cur] = true;
		cur = f[cur][0];
	}

	// for(int d : e[1]) {
	// 	res[1] += 1LL * siz[d] * (siz[d] - 1) / 2;
	// }
	// int cur = get(2, 2);
	// int sum = 1;
	// vector<int> v;
	// v.push_back(1);
	// for(int d : e[1]) {
	// 	if(d == cur) v.push_back(siz[d] - siz[2]);
	// 	else v.push_back(siz[d]);
	// 	sum += v.back();
	// }
	// for(int a : v) {
	// 	res[2] += 1LL * a * (sum - a);
	// }
	// res[2] /= 2;
	// siz[1] -= siz[cur];
	// vis[0] = true;
	// cur = 2;
	// while(!vis[cur]) {
	// 	vis[cur] = true;
	// 	cur = f[cur][0];
	// }

	int x = 2, y = 1;
	for(int i = 3; i <= n + 1; i++) {
		if(i == n + 1) {
			res[i] = 1;
			break;
		}
		if(vis[i]) {
			res[i] = 0;
			continue;
		}
		if(get(i, dep[x]) == x) {
			res[i] = 1LL * siz[y] * (siz[x] - siz[i]);
			int cur = i;
			while(!vis[cur]) {
				vis[cur] = true;
				cur = f[cur][0];
			}
			x = i;
		}
		else if(get(i, dep[y]) == y) {
			if(y == 1 && get(2, 2) == get(i, 2)) {
				res[i] = 1LL * siz[x] * siz[y];
				break;
			}
			res[i] = 1LL * siz[x] * (siz[y] - siz[i]);
			int cur = i;
			while(!vis[cur]) {
				vis[cur] = true;
				cur = f[cur][0];
			}
			y = i;
		}
		else {
			res[i] = 1LL * siz[x] * siz[y];
			break;
		}
	}
	for(int i = 1; i <= n + 1; i++) {
		printf("%lld ", res[i]);
	}
	puts("");

}

int main() {
	// freopen("in.txt", "r", stdin);
	int t; cin >> t; while(t--)
    solve();
    return 0;
}
### Prompt

Please formulate a cpp solution to the following problem:

You are given a tree with n nodes, numerated from 0 to n-1. For each k between 0 and n, inclusive, you have to count the number of unordered pairs (u,v), u ≠ v, such that the MEX of all the node labels in the shortest path from u to v (including end points) is k.

The MEX of a sequence of integers is the smallest non-negative integer that does not belong to the sequence.

Input

The first line contains a single integer t (1 ≤ t ≤ 10^4) — the number of test cases. 

The first line of each test case contains a single integer n (2 ≤ n ≤ 2 ⋅ 10^{5}).

The next n-1 lines of each test case describe the tree that has to be constructed. These lines contain two integers u and v (0 ≤ u,v ≤ n-1) denoting an edge between u and v (u ≠ v).

It is guaranteed that the given edges form a tree.

It is also guaranteed that the sum of n for all test cases does not exceed 2 ⋅ 10^{5}.

Output

For each test case, print n+1 integers: the number of paths in the tree, such that the MEX of all the node labels in that path is k for each k from 0 to n.

Example

Input


2
4
0 1
0 2
2 3
2
1 0


Output


1 2 1 1 1 
0 0 1 

Note

  1. In example case 1, <image>
    * For k = 0, there is 1 path that is from 2 to 3 as MEX([2, 3]) = 0. 
    * For k = 1, there are 2 paths that is from 0 to 2 as MEX([0, 2]) = 1 and 0 to 3 as MEX([0, 2, 3]) = 1. 
    * For k = 2, there is 1 path that is from 0 to 1 as MEX([0, 1]) = 2. 
    * For k = 3, there is 1 path that is from 1 to 2 as MEX([1, 0, 2]) = 3 
    * For k = 4, there is 1 path that is from 1 to 3 as MEX([1, 0, 2, 3]) = 4. 
  2. In example case 2, <image>
    * For k = 0, there are no such paths. 
    * For k = 1, there are no such paths. 
    * For k = 2, there is 1 path that is from 0 to 1 as MEX([0, 1]) = 2. 

### Response

```cpp
#include<bits/stdc++.h>
using namespace std;

typedef long long LL;
typedef pair<int, int> PII;
const int N = 2e5 + 100, M = 1e5 + 100;
const int inf = 0x3f3f3f3f;
const LL INF = 0x3f3f3f3f3f3f3f3f;
#define x first
#define y second
const int mod = 1e9 + 7;
#define gcd __gcd
const double eps = 1e-8;
const double PI = acos(-1.0);

LL res[N];
vector<int> e[N];
int siz[N], f[N][35];
int dep[N];
bool vis[N];

void dfs(int u, int fa, int d) {
	dep[u] = d;
	f[u][0] = fa;
	siz[u] = 1;
	for(int i = 1; i <= 30; i++) {
		f[u][i] = f[f[u][i - 1]][i - 1];
	}
	for(auto v : e[u]) {
		if(v == fa) continue;
		dfs(v, u, d + 1);
		siz[u] += siz[v];
	}
}

int get(int x, int d) {
	int now = x;
	for(int i = 30; i >= 0; i--) {
		// if(now == 3 && d == 2) cout << dep[f[x][i]] << endl;
		if(dep[f[x][i]] >= d) {
			x = f[x][i];
		}
	}
	// if(now == 3 && d == 2) cout << "namo " << x << endl;
	return x;
}

void solve() {
	int n;
	scanf("%d", &n);
	for(int i = 1; i <= n + 1; i++) {
		res[i] = 0;
		e[i].clear();
		vis[i] = false;
	}
	for(int i = 1; i < n; i++) {
		int u, v;
		scanf("%d%d", &u, &v);
		u++; v++;
		e[u].push_back(v);
		e[v].push_back(u);
	}
	dfs(1, 0, 1);

	for(auto v : e[1]) {
		res[1] += 1LL * siz[v] * (siz[v] - 1) / 2;
	}

	int cur = 2;
	while(f[cur][0] != 1) {
		cur = f[cur][0];
	}
	int sum = 0;
	for(auto d : e[1]) {
		if(d == cur) sum += siz[d] - siz[2];
		else sum += siz[d];
	}
	for(auto d : e[1]) {
		if(d == cur) res[2] += 1LL * (siz[d] - siz[2]) * (sum - (siz[d] - siz[2]));
		else res[2] += 1LL * siz[d] * (sum - siz[d]);
	}
	res[2] /= 2;
	res[2] += sum;
	siz[1] -= siz[cur];

	cur = 2;
	while(!vis[cur]) {
		vis[cur] = true;
		cur = f[cur][0];
	}

	// for(int d : e[1]) {
	// 	res[1] += 1LL * siz[d] * (siz[d] - 1) / 2;
	// }
	// int cur = get(2, 2);
	// int sum = 1;
	// vector<int> v;
	// v.push_back(1);
	// for(int d : e[1]) {
	// 	if(d == cur) v.push_back(siz[d] - siz[2]);
	// 	else v.push_back(siz[d]);
	// 	sum += v.back();
	// }
	// for(int a : v) {
	// 	res[2] += 1LL * a * (sum - a);
	// }
	// res[2] /= 2;
	// siz[1] -= siz[cur];
	// vis[0] = true;
	// cur = 2;
	// while(!vis[cur]) {
	// 	vis[cur] = true;
	// 	cur = f[cur][0];
	// }

	int x = 2, y = 1;
	for(int i = 3; i <= n + 1; i++) {
		if(i == n + 1) {
			res[i] = 1;
			break;
		}
		if(vis[i]) {
			res[i] = 0;
			continue;
		}
		if(get(i, dep[x]) == x) {
			res[i] = 1LL * siz[y] * (siz[x] - siz[i]);
			int cur = i;
			while(!vis[cur]) {
				vis[cur] = true;
				cur = f[cur][0];
			}
			x = i;
		}
		else if(get(i, dep[y]) == y) {
			if(y == 1 && get(2, 2) == get(i, 2)) {
				res[i] = 1LL * siz[x] * siz[y];
				break;
			}
			res[i] = 1LL * siz[x] * (siz[y] - siz[i]);
			int cur = i;
			while(!vis[cur]) {
				vis[cur] = true;
				cur = f[cur][0];
			}
			y = i;
		}
		else {
			res[i] = 1LL * siz[x] * siz[y];
			break;
		}
	}
	for(int i = 1; i <= n + 1; i++) {
		printf("%lld ", res[i]);
	}
	puts("");

}

int main() {
	// freopen("in.txt", "r", stdin);
	int t; cin >> t; while(t--)
    solve();
    return 0;
}
```