#include <stdio.h>
#include <algorithm>
#include <vector>
#include <memory.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <string.h>
#include <string>
#include <math.h>
using namespace std;
typedef long long ll;
const int INF = 1e9;
const int MOD = 1e9 + 7;

vector<int> adj[200100];
int parent[200100];
int siz[200100];

int inpath[200100];
ll pcnt[200100];
ll ans[200100];

void init(int n){
	for (int i = 0; i < n + 5; i++){
		adj[i].clear();
		inpath[i] = pcnt[i] = ans[i] = 0;
	}
}

void dfs(int now, int p){
	parent[now] = p;
	siz[now] = 1;
	for (int nxt : adj[now]){
		if (nxt == p) continue;
		dfs(nxt, now);
		siz[now] += siz[nxt];
	}
}

int connect(int now){
	inpath[now] = 1;
	if (parent[now] == 0) siz[0] -= siz[now];
	
	if (inpath[parent[now]] == 1){
		return parent[now];
	}
	return connect(parent[now]);
}

void compute(int n){
	ll nxtsum = n - 1;
	int l, r;

	pcnt[0] = n - 1;
	for (int nxt : adj[0]){
		nxtsum -= siz[nxt];
		pcnt[0] += siz[nxt] * nxtsum;
	}

	l = 0;
	r = 0;
	inpath[0] = 1;
	for (int i = 1; i < n; i++){
		if (inpath[i] == 0){
			int res = connect(i);
			
			if (res == l) l = i;
			else if (res == r) r = i;
			else break;
		}
		pcnt[i] = (ll)siz[l] * siz[r];
	}

	for (int nxt : adj[0]){
		ans[0] += (ll)siz[nxt] * (siz[nxt] - 1) / 2;
	}
	for (int i = 1; i <= n; i++){
		ans[i] = pcnt[i - 1] - pcnt[i];
	}
}

int main()
{
	int t;

	scanf("%d", &t);

	while (t--){
		int n;
		scanf("%d", &n);
		init(n);
		for (int i = 0; i < n - 1; i++){
			int x, y;
			scanf("%d %d", &x, &y);
			adj[x].push_back(y);
			adj[y].push_back(x);
		}
		dfs(0, -1);
		compute(n);

		for (int i = 0; i <= n; i++){
			printf("%lld ", ans[i]);
		}
		printf("\n");
	}

	return 0;
}

### Prompt

Create a solution in cpp for 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 <stdio.h>
#include <algorithm>
#include <vector>
#include <memory.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <string.h>
#include <string>
#include <math.h>
using namespace std;
typedef long long ll;
const int INF = 1e9;
const int MOD = 1e9 + 7;

vector<int> adj[200100];
int parent[200100];
int siz[200100];

int inpath[200100];
ll pcnt[200100];
ll ans[200100];

void init(int n){
	for (int i = 0; i < n + 5; i++){
		adj[i].clear();
		inpath[i] = pcnt[i] = ans[i] = 0;
	}
}

void dfs(int now, int p){
	parent[now] = p;
	siz[now] = 1;
	for (int nxt : adj[now]){
		if (nxt == p) continue;
		dfs(nxt, now);
		siz[now] += siz[nxt];
	}
}

int connect(int now){
	inpath[now] = 1;
	if (parent[now] == 0) siz[0] -= siz[now];
	
	if (inpath[parent[now]] == 1){
		return parent[now];
	}
	return connect(parent[now]);
}

void compute(int n){
	ll nxtsum = n - 1;
	int l, r;

	pcnt[0] = n - 1;
	for (int nxt : adj[0]){
		nxtsum -= siz[nxt];
		pcnt[0] += siz[nxt] * nxtsum;
	}

	l = 0;
	r = 0;
	inpath[0] = 1;
	for (int i = 1; i < n; i++){
		if (inpath[i] == 0){
			int res = connect(i);
			
			if (res == l) l = i;
			else if (res == r) r = i;
			else break;
		}
		pcnt[i] = (ll)siz[l] * siz[r];
	}

	for (int nxt : adj[0]){
		ans[0] += (ll)siz[nxt] * (siz[nxt] - 1) / 2;
	}
	for (int i = 1; i <= n; i++){
		ans[i] = pcnt[i - 1] - pcnt[i];
	}
}

int main()
{
	int t;

	scanf("%d", &t);

	while (t--){
		int n;
		scanf("%d", &n);
		init(n);
		for (int i = 0; i < n - 1; i++){
			int x, y;
			scanf("%d %d", &x, &y);
			adj[x].push_back(y);
			adj[y].push_back(x);
		}
		dfs(0, -1);
		compute(n);

		for (int i = 0; i <= n; i++){
			printf("%lld ", ans[i]);
		}
		printf("\n");
	}

	return 0;
}

```