#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
template <typename T> inline void read(T &FF) {
	int RR = 1; FF = 0; char CH = getchar();
	for(; !isdigit(CH); CH = getchar()) if(CH == '-') RR = -RR;
	for(; isdigit(CH); CH = getchar()) FF = FF * 10 + CH - 48;
	FF *= RR;
}
inline void file(string str) {
	freopen((str + ".in").c_str(), "r", stdin);
	freopen((str + ".out").c_str(), "w", stdout);
}
const int N = 2e5 + 10, Log = 22;
int n, size[N], flag[N], di[N], d; LL res[N];
int now, fst[N], nxt[N << 1], num[N << 1], fa[N], f[N][Log], dep[N];
void add(int u, int v) {
	nxt[++now] = fst[u], fst[u] = now, num[now] = v;
	nxt[++now] = fst[v], fst[v] = now, num[now] = u;
}
void dfs(int x) {
	di[x] = ++d, size[x] = 1, dep[x] = dep[fa[x]] + 1; f[x][0] = fa[x];
	for(int i = 1; i < Log; i++) f[x][i] = f[f[x][i - 1]][i - 1];
	for(int i = fst[x]; i; i = nxt[i])
		if(num[i] != fa[x]) fa[num[i]] = x, dfs(num[i]), size[x] += size[num[i]];	
}
bool checkson(int x, int y) {
	return di[y] >= di[x] && di[y] <= di[x] + size[x] - 1;
}
int walk(int x, int y) {
	for(int i = Log - 1; i >= 0; i--)
		if(dep[f[x][i]] > dep[y])
			x = f[x][i];
	return x;
}
int main() {
	//file("");
	int T; read(T);
	while(T--) {
		read(n); int u, v; d = 0, now = 0;
		for(int i = 1; i < n; i++)
			read(u), read(v), add(u + 1, v + 1);
		dfs(1); res[0] = n * 1LL * (n - 1) / 2;
		res[1] = 0; LL sum = 1;
		for(int i = fst[1]; i; i = nxt[i])
			res[1] += size[num[i]] * sum, sum += size[num[i]];
		int li = 1, ri = 1; flag[1] = 1;
		for(int i = 2; i <= n; i++) {
			if(!flag[i]) {
				if(checkson(li, i) && (!checkson(ri, i) || (checkson(ri, i) && checkson(ri, li)))) {
					int p = i;
					while(p != li) {
						if(flag[p]) goto ed;
						flag[p] = 1, p = fa[p];
					}
					li = i;
				}
				else if(checkson(ri, i)) {
					int p = i;
					while(p != ri) {
						if(flag[p]) goto ed;
						flag[p] = 1, p = fa[p];
					}
					ri = i;
				}
				else break;
			}
			if(checkson(li, ri)) {
				LL si = n - size[walk(ri, li)];
				//cout << li << " " << ri << " " << si << " " << size[ri] << endl;
				res[i] = si * size[ri];
			}
			else if(checkson(ri, li)) {
				LL si = n - size[walk(li, ri)];
				//cout << li << " " << ri << " " << si << " " << size[li] << endl;
				res[i] = si * size[li];
			}
			else res[i] = size[li] * 1LL * size[ri];
			//cout << i << " " << li - 1 << " " << ri - 1 << endl;
		}
		//for(int i = 0; i <= n; i++) printf("%lld ", res[i]); puts("");
		ed:;
		for(int i = 1; i <= n; i++) printf("%lld ", res[i - 1] - res[i]); printf("%lld\n", res[n]);
		for(int i = 1; i <= now; i++)
			num[i] = nxt[i] = 0;
		for(int i = 1; i <= n; i++)
			for(int j = 0; j < Log; j++) f[i][j] = 0;
		for(int i = 1; i <= n; i++)
			fst[i] = 0, flag[i] = 0, res[i] = 0;
	}
	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;
template <typename T> inline void read(T &FF) {
	int RR = 1; FF = 0; char CH = getchar();
	for(; !isdigit(CH); CH = getchar()) if(CH == '-') RR = -RR;
	for(; isdigit(CH); CH = getchar()) FF = FF * 10 + CH - 48;
	FF *= RR;
}
inline void file(string str) {
	freopen((str + ".in").c_str(), "r", stdin);
	freopen((str + ".out").c_str(), "w", stdout);
}
const int N = 2e5 + 10, Log = 22;
int n, size[N], flag[N], di[N], d; LL res[N];
int now, fst[N], nxt[N << 1], num[N << 1], fa[N], f[N][Log], dep[N];
void add(int u, int v) {
	nxt[++now] = fst[u], fst[u] = now, num[now] = v;
	nxt[++now] = fst[v], fst[v] = now, num[now] = u;
}
void dfs(int x) {
	di[x] = ++d, size[x] = 1, dep[x] = dep[fa[x]] + 1; f[x][0] = fa[x];
	for(int i = 1; i < Log; i++) f[x][i] = f[f[x][i - 1]][i - 1];
	for(int i = fst[x]; i; i = nxt[i])
		if(num[i] != fa[x]) fa[num[i]] = x, dfs(num[i]), size[x] += size[num[i]];	
}
bool checkson(int x, int y) {
	return di[y] >= di[x] && di[y] <= di[x] + size[x] - 1;
}
int walk(int x, int y) {
	for(int i = Log - 1; i >= 0; i--)
		if(dep[f[x][i]] > dep[y])
			x = f[x][i];
	return x;
}
int main() {
	//file("");
	int T; read(T);
	while(T--) {
		read(n); int u, v; d = 0, now = 0;
		for(int i = 1; i < n; i++)
			read(u), read(v), add(u + 1, v + 1);
		dfs(1); res[0] = n * 1LL * (n - 1) / 2;
		res[1] = 0; LL sum = 1;
		for(int i = fst[1]; i; i = nxt[i])
			res[1] += size[num[i]] * sum, sum += size[num[i]];
		int li = 1, ri = 1; flag[1] = 1;
		for(int i = 2; i <= n; i++) {
			if(!flag[i]) {
				if(checkson(li, i) && (!checkson(ri, i) || (checkson(ri, i) && checkson(ri, li)))) {
					int p = i;
					while(p != li) {
						if(flag[p]) goto ed;
						flag[p] = 1, p = fa[p];
					}
					li = i;
				}
				else if(checkson(ri, i)) {
					int p = i;
					while(p != ri) {
						if(flag[p]) goto ed;
						flag[p] = 1, p = fa[p];
					}
					ri = i;
				}
				else break;
			}
			if(checkson(li, ri)) {
				LL si = n - size[walk(ri, li)];
				//cout << li << " " << ri << " " << si << " " << size[ri] << endl;
				res[i] = si * size[ri];
			}
			else if(checkson(ri, li)) {
				LL si = n - size[walk(li, ri)];
				//cout << li << " " << ri << " " << si << " " << size[li] << endl;
				res[i] = si * size[li];
			}
			else res[i] = size[li] * 1LL * size[ri];
			//cout << i << " " << li - 1 << " " << ri - 1 << endl;
		}
		//for(int i = 0; i <= n; i++) printf("%lld ", res[i]); puts("");
		ed:;
		for(int i = 1; i <= n; i++) printf("%lld ", res[i - 1] - res[i]); printf("%lld\n", res[n]);
		for(int i = 1; i <= now; i++)
			num[i] = nxt[i] = 0;
		for(int i = 1; i <= n; i++)
			for(int j = 0; j < Log; j++) f[i][j] = 0;
		for(int i = 1; i <= n; i++)
			fst[i] = 0, flag[i] = 0, res[i] = 0;
	}
	return 0;
}
```