#include<bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef long double ld;
 
#define F first
#define S second
 
const int MOD = 1e9 + 7;//XXX
const int C = 26;//XXX
 
void add(int &x, int y){
	x += y;
	while (x >= MOD) x -= MOD;
	while (x < 0) x += MOD;
}
 
int fix(int x){
	while (x >= MOD) x -= MOD;
	while (x < 0) x += MOD;
	return x;
}
 
int pw(int a, int b){
	int ret = 1;
	while (b){
		if (b & 1)
			ret = 1ll*ret*a%MOD;
		b >>= 1;
		a = 1ll*a*a%MOD;
	}
	return ret;
}
 
const int MAXN = 2e5 + 10;

vector<int> adj[MAXN];
int n, par[MAXN], sz[MAXN], mark[MAXN];
ll ans[MAXN];

void clr() {
	for(int i = 0; i < n; i++)
		adj[i].clear();
	memset(mark, -1, 4*n);
}

void dfs(int v, int p) {
	if(~p)
		adj[v].erase(find(adj[v].begin(), adj[v].end(), p));
	sz[v] = 1;
	for(int u : adj[v]) {
		par[u] = v;
		dfs(u, v);
		sz[v] += sz[u];
	}
}

ll ch2(ll x) {
	return x * (x-1) / 2;
}

void solve() {
	cin >> n;
	clr();
	for(int i = 1; i < n; i++) {
		int a, b; cin >> a >> b;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	dfs(0, -1);
	
	ans[0] = ch2(n);
	ans[1] = ch2(n);
	for(int u : adj[0])
		ans[1] -= ch2(sz[u]);
	mark[0] = 0;
	int A = 0, B = 0;
	for(int v = 1; v < n; v++) {
		int u = v;
		while(mark[u] == -1) {
			mark[u] = v;
			if(par[u] == A || par[u] == B) {
				sz[par[u]] -= sz[u];
			}
			u = par[u];
		}
		if(u != A && u != B && mark[v] == v) {
			for(int i = v+1; i <= n; i++)
				ans[i] = 0;
			break;
		}
		if(u == A) {
			A = v;
		} else if(u == B) {
			B = v;
		}
		ans[v+1] = (ll) sz[A] * sz[B];
	}
	
	for(int i = 0; i < n; i++) 
		ans[i] -= ans[i+1];
	
	for(int i = 0; i <= n; i++) {
		assert(ans[i] >= 0);
		cout << ans[i] << " ";
	}
	cout << "\n";
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	//cout << fixed << setprecision(6);
	
	int te = 1;	
	cin >> te;
	for (int w = 1; w <= te; w++){
		//cout << "Case #" << w << ": ";
		solve();
	}
	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;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef long double ld;
 
#define F first
#define S second
 
const int MOD = 1e9 + 7;//XXX
const int C = 26;//XXX
 
void add(int &x, int y){
	x += y;
	while (x >= MOD) x -= MOD;
	while (x < 0) x += MOD;
}
 
int fix(int x){
	while (x >= MOD) x -= MOD;
	while (x < 0) x += MOD;
	return x;
}
 
int pw(int a, int b){
	int ret = 1;
	while (b){
		if (b & 1)
			ret = 1ll*ret*a%MOD;
		b >>= 1;
		a = 1ll*a*a%MOD;
	}
	return ret;
}
 
const int MAXN = 2e5 + 10;

vector<int> adj[MAXN];
int n, par[MAXN], sz[MAXN], mark[MAXN];
ll ans[MAXN];

void clr() {
	for(int i = 0; i < n; i++)
		adj[i].clear();
	memset(mark, -1, 4*n);
}

void dfs(int v, int p) {
	if(~p)
		adj[v].erase(find(adj[v].begin(), adj[v].end(), p));
	sz[v] = 1;
	for(int u : adj[v]) {
		par[u] = v;
		dfs(u, v);
		sz[v] += sz[u];
	}
}

ll ch2(ll x) {
	return x * (x-1) / 2;
}

void solve() {
	cin >> n;
	clr();
	for(int i = 1; i < n; i++) {
		int a, b; cin >> a >> b;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	dfs(0, -1);
	
	ans[0] = ch2(n);
	ans[1] = ch2(n);
	for(int u : adj[0])
		ans[1] -= ch2(sz[u]);
	mark[0] = 0;
	int A = 0, B = 0;
	for(int v = 1; v < n; v++) {
		int u = v;
		while(mark[u] == -1) {
			mark[u] = v;
			if(par[u] == A || par[u] == B) {
				sz[par[u]] -= sz[u];
			}
			u = par[u];
		}
		if(u != A && u != B && mark[v] == v) {
			for(int i = v+1; i <= n; i++)
				ans[i] = 0;
			break;
		}
		if(u == A) {
			A = v;
		} else if(u == B) {
			B = v;
		}
		ans[v+1] = (ll) sz[A] * sz[B];
	}
	
	for(int i = 0; i < n; i++) 
		ans[i] -= ans[i+1];
	
	for(int i = 0; i <= n; i++) {
		assert(ans[i] >= 0);
		cout << ans[i] << " ";
	}
	cout << "\n";
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	//cout << fixed << setprecision(6);
	
	int te = 1;	
	cin >> te;
	for (int w = 1; w <= te; w++){
		//cout << "Case #" << w << ": ";
		solve();
	}
	return 0;
}

```