#include <bits/stdc++.h>

using namespace std;

#define x first
#define y second
#define mp make_pair
#define pb push_back

typedef long long ll;

const ll MOD = 1e9+7;
const ll INF = 1e9+5;

vector <int> v[200005];
int p[200005][20];
int dub[200005];
int siz[200005];

void dfs(int node, int par, int d) {
	dub[node] = d;
	p[node][0] = par;
	siz[node] = 1;
	for (int i=0 ; i<v[node].size() ; i++) {
		int nx = v[node][i];
		if (nx == par) continue;
		dfs(nx, node, d+1);
		siz[node] += siz[nx];
	}
}

int lca(int x, int y) {
	if (dub[x] < dub[y]) swap(x, y);
	for (int i=19 ; i>=0 ; i--) {
		if (p[x][i] == -1) continue;
		if (dub[p[x][i]] >= dub[y]) x = p[x][i];
	}
	if (x == y) return x;
	for (int i=19 ; i>=0 ; i--) {
		if (p[x][i] == -1) continue;
		if (p[x][i] != p[y][i]) {
			x = p[x][i];
			y = p[y][i];
		}
	}
	return p[x][0];
}

int elca(int x, int y) {
	if (dub[x] < dub[y]) swap(x, y);
	for (int i=19 ; i>=0 ; i--) {
		if (dub[p[x][i]] > dub[y]) x = p[x][i];
	}
	return x;
}

int main() {
	int t;
	scanf("%d", &t);
	while (t--) {
		int n;
		scanf("%d", &n);
		for (int i=0 ; i<n-1 ; i++) {
			int x, y;
			scanf("%d%d", &x, &y);
			v[x].pb(y);
			v[y].pb(x);
		}
		dfs(0, -1, 0);
		ll cnt = 0;
		for (int i=0 ; i<v[0].size() ; i++) {
			ll m = siz[v[0][i]];
			cnt += m*(m-1)/2;
		}
		printf("%lld ", cnt);
		for (int j=1 ; j<20 ; j++) {
			for (int i=0 ; i<n ; i++) {
				if (p[i][j-1] == -1) p[i][j] = -1;
				else p[i][j] = p[p[i][j-1]][j-1];
			}
		}
		int l = 0;
		int r = 0;
		bool ok = true;
		for (int i=1 ; i<n ; i++) {
			//cout <<endl<<" i = "<<i<<endl;
			if (!ok) {
				printf("0 ");
				continue;
			}
			if (i == 1) {
				ll cnt = 0;
				ll sum = 1;
				for (int i=0 ; i<v[0].size() ; i++) {
					int nx = v[0][i];
					ll si = siz[nx];
					if (lca(1, nx) == nx) si -= siz[1];
					cnt += sum * si;
					sum += si;
				}
				printf("%lld ", cnt);
				l = 1;
				continue;
			}
			ll x = siz[l];
			ll y = siz[r];
			//cout <<"l, r = "<<l<<" "<<r<<endl;
			if (lca(l, r) == r) {
				y -= siz[elca(l, r)];
			}
			ll o = 0;
			if (lca(i, l) == l) {
			//	cout <<"...\n";
				x -= siz[i];
				o = x*y;
				l = i;
			} else if (lca(i, r) == r and (lca(l, r) != r or lca(l, i) == r)) {
			//	cout <<":::\n";
				y -= siz[i];
				o = x*y;
				r = i;
			} else {
				if (lca(i, r) != i and lca(i, l) != i) {
				//	cout <<"sus\n";
					o = x*y;
					ok = false;
				}
			//	cout <<"amogus\n";
			}
			printf("%lld ", o);
		}
		int o = 1;
		for (int i=0 ; i<n ; i++) {
			if (v[i].size() > 2) o = 0;
		}
		printf("%d\n", o);
		for (int i=0 ; i<n ; i++) v[i].clear();
	}	
	return 0;
}
### Prompt

Your task is to create 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;

#define x first
#define y second
#define mp make_pair
#define pb push_back

typedef long long ll;

const ll MOD = 1e9+7;
const ll INF = 1e9+5;

vector <int> v[200005];
int p[200005][20];
int dub[200005];
int siz[200005];

void dfs(int node, int par, int d) {
	dub[node] = d;
	p[node][0] = par;
	siz[node] = 1;
	for (int i=0 ; i<v[node].size() ; i++) {
		int nx = v[node][i];
		if (nx == par) continue;
		dfs(nx, node, d+1);
		siz[node] += siz[nx];
	}
}

int lca(int x, int y) {
	if (dub[x] < dub[y]) swap(x, y);
	for (int i=19 ; i>=0 ; i--) {
		if (p[x][i] == -1) continue;
		if (dub[p[x][i]] >= dub[y]) x = p[x][i];
	}
	if (x == y) return x;
	for (int i=19 ; i>=0 ; i--) {
		if (p[x][i] == -1) continue;
		if (p[x][i] != p[y][i]) {
			x = p[x][i];
			y = p[y][i];
		}
	}
	return p[x][0];
}

int elca(int x, int y) {
	if (dub[x] < dub[y]) swap(x, y);
	for (int i=19 ; i>=0 ; i--) {
		if (dub[p[x][i]] > dub[y]) x = p[x][i];
	}
	return x;
}

int main() {
	int t;
	scanf("%d", &t);
	while (t--) {
		int n;
		scanf("%d", &n);
		for (int i=0 ; i<n-1 ; i++) {
			int x, y;
			scanf("%d%d", &x, &y);
			v[x].pb(y);
			v[y].pb(x);
		}
		dfs(0, -1, 0);
		ll cnt = 0;
		for (int i=0 ; i<v[0].size() ; i++) {
			ll m = siz[v[0][i]];
			cnt += m*(m-1)/2;
		}
		printf("%lld ", cnt);
		for (int j=1 ; j<20 ; j++) {
			for (int i=0 ; i<n ; i++) {
				if (p[i][j-1] == -1) p[i][j] = -1;
				else p[i][j] = p[p[i][j-1]][j-1];
			}
		}
		int l = 0;
		int r = 0;
		bool ok = true;
		for (int i=1 ; i<n ; i++) {
			//cout <<endl<<" i = "<<i<<endl;
			if (!ok) {
				printf("0 ");
				continue;
			}
			if (i == 1) {
				ll cnt = 0;
				ll sum = 1;
				for (int i=0 ; i<v[0].size() ; i++) {
					int nx = v[0][i];
					ll si = siz[nx];
					if (lca(1, nx) == nx) si -= siz[1];
					cnt += sum * si;
					sum += si;
				}
				printf("%lld ", cnt);
				l = 1;
				continue;
			}
			ll x = siz[l];
			ll y = siz[r];
			//cout <<"l, r = "<<l<<" "<<r<<endl;
			if (lca(l, r) == r) {
				y -= siz[elca(l, r)];
			}
			ll o = 0;
			if (lca(i, l) == l) {
			//	cout <<"...\n";
				x -= siz[i];
				o = x*y;
				l = i;
			} else if (lca(i, r) == r and (lca(l, r) != r or lca(l, i) == r)) {
			//	cout <<":::\n";
				y -= siz[i];
				o = x*y;
				r = i;
			} else {
				if (lca(i, r) != i and lca(i, l) != i) {
				//	cout <<"sus\n";
					o = x*y;
					ok = false;
				}
			//	cout <<"amogus\n";
			}
			printf("%lld ", o);
		}
		int o = 1;
		for (int i=0 ; i<n ; i++) {
			if (v[i].size() > 2) o = 0;
		}
		printf("%d\n", o);
		for (int i=0 ; i<n ; i++) v[i].clear();
	}	
	return 0;
}
```