/*
yaswanth phani kommineni
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef long double ld;
#define pb push_back
#define mpa make_pair
#define endl '\n'

const ll M = 2e5+1;
vector < vector <ll> > g(M);
vector <bool> vis(M);
vector <ll> d(M),ans(M),vt(M),lt(M),sz(M),col(M);
ll timer = 0;

void ___(ll u){
	vis[u] = true;
	for(auto x : g[u]){
		if(vis[x]) continue;
		col[x] = col[u];
		___(x);
	}
}

void _(ll u){
	vt[u] = (++timer);
	vis[u] = true;
	sz[u] = 1;
	for(auto x : g[u]){
		if(vis[x]) continue;
		_(x);
		sz[u] += sz[x];
	}
	lt[u] = timer;
}

void __(ll u){
	vis[u] = true;
	for(auto x : g[u]){
		if(vis[x]) continue;
		if(d[u] == 1) d[x] = 1;
		__(x);
	}
}

bool isParent(ll v,ll p){
	return (vt[p]<=vt[v] && lt[v]<=lt[p]);
}

void solve(){
	ll n;
	cin >> n;
	for(ll i=0;i<n-1;i++){
		ll u,v;
		cin >> u >> v;
		g[u].pb(v);
		g[v].pb(u);
	}
	_(0);
	for(auto x : g[0]){
		ans[0] += sz[x]*(sz[x]-1)/2;
	}
	for(ll i=0;i<n;i++){
		vis[i] = false;
	}
	d[1] = 1;
	__(0);
	ll k = 0;
	for(ll i=0;i<n;i++){
		k += (d[i] == 0);
	}
	ans[1] = (k)*(k-1)/2;
	for(ll i=0;i<n;i++){
		vis[i] = false;
		d[i] = 0;
	}
	vis[0] = true;
	for(auto x : g[0]){
		col[x] = x;
		___(x);
	}
	for(auto x : g[0]){
		if(x!=col[1]){
			ans[1] -= (sz[x])*(sz[x]-1)/2;
		}
		else{
			ans[1] -= (sz[x]-sz[1])*(sz[x]-sz[1]-1)/2;
		}
	}
	for(ll i=0;i<n;i++){
		vis[i] = false;
	}
	ll b = 1,c = -1;
	ans[n] = 1;
	for(ll i=2;i<n;i++){
		if(c == -1){
			if(!isParent(b,i)){
				if(isParent(i,b)){
					ans[i] = (sz[0]-sz[col[b]])*(sz[b]-sz[i]);
					b = i;
				}
				else{
					if(col[i]==col[b]){
						ans[n] = 0;
						ans[i] = (sz[0]-sz[col[b]])*sz[b];
						break;
					}
					else{
						ans[i] = (sz[0]-sz[col[b]]-sz[i])*sz[b];
						c = i;
					}
				}
			}
		}
		else{
			if(!isParent(b,i) && !isParent(c,i)){
				if(isParent(i,b)){
					ans[i] = sz[c]*(sz[b]-sz[i]);
					b = i;
				}
				else if(isParent(i,c)){
					ans[i] = sz[b]*(sz[c]-sz[i]);
					c = i;
				}
				else{
					ans[n] = 0;
					ans[i] = sz[c]*sz[b];
					break;
				}
			}
		}
	}
	for(ll i=0;i<=n;i++){
		cout << ans[i] << " ";
	}
	cout << endl;
	for(ll i=0;i<n;i++){
		g[i].clear();
		sz[i] = 0;
		col[i] =0;
		vis[i] = false;
		ans[i] = 0;
		vt[i] = 0;
		lt[i] = 0;
		d[i] = 0;
		timer = 0;	
	}
}

int main(){
	//freopen("input.txt","r",stdin);
	//freopen("output.txt","w",stdout);
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int tc;
	tc = 1;
	cin >> tc;
	for(int i=1;i<=tc;i++){
		//cout << "Case #" << i << ": ";
		solve();
	}
	return 0;
}

### Prompt

Your challenge is to write 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
/*
yaswanth phani kommineni
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef long double ld;
#define pb push_back
#define mpa make_pair
#define endl '\n'

const ll M = 2e5+1;
vector < vector <ll> > g(M);
vector <bool> vis(M);
vector <ll> d(M),ans(M),vt(M),lt(M),sz(M),col(M);
ll timer = 0;

void ___(ll u){
	vis[u] = true;
	for(auto x : g[u]){
		if(vis[x]) continue;
		col[x] = col[u];
		___(x);
	}
}

void _(ll u){
	vt[u] = (++timer);
	vis[u] = true;
	sz[u] = 1;
	for(auto x : g[u]){
		if(vis[x]) continue;
		_(x);
		sz[u] += sz[x];
	}
	lt[u] = timer;
}

void __(ll u){
	vis[u] = true;
	for(auto x : g[u]){
		if(vis[x]) continue;
		if(d[u] == 1) d[x] = 1;
		__(x);
	}
}

bool isParent(ll v,ll p){
	return (vt[p]<=vt[v] && lt[v]<=lt[p]);
}

void solve(){
	ll n;
	cin >> n;
	for(ll i=0;i<n-1;i++){
		ll u,v;
		cin >> u >> v;
		g[u].pb(v);
		g[v].pb(u);
	}
	_(0);
	for(auto x : g[0]){
		ans[0] += sz[x]*(sz[x]-1)/2;
	}
	for(ll i=0;i<n;i++){
		vis[i] = false;
	}
	d[1] = 1;
	__(0);
	ll k = 0;
	for(ll i=0;i<n;i++){
		k += (d[i] == 0);
	}
	ans[1] = (k)*(k-1)/2;
	for(ll i=0;i<n;i++){
		vis[i] = false;
		d[i] = 0;
	}
	vis[0] = true;
	for(auto x : g[0]){
		col[x] = x;
		___(x);
	}
	for(auto x : g[0]){
		if(x!=col[1]){
			ans[1] -= (sz[x])*(sz[x]-1)/2;
		}
		else{
			ans[1] -= (sz[x]-sz[1])*(sz[x]-sz[1]-1)/2;
		}
	}
	for(ll i=0;i<n;i++){
		vis[i] = false;
	}
	ll b = 1,c = -1;
	ans[n] = 1;
	for(ll i=2;i<n;i++){
		if(c == -1){
			if(!isParent(b,i)){
				if(isParent(i,b)){
					ans[i] = (sz[0]-sz[col[b]])*(sz[b]-sz[i]);
					b = i;
				}
				else{
					if(col[i]==col[b]){
						ans[n] = 0;
						ans[i] = (sz[0]-sz[col[b]])*sz[b];
						break;
					}
					else{
						ans[i] = (sz[0]-sz[col[b]]-sz[i])*sz[b];
						c = i;
					}
				}
			}
		}
		else{
			if(!isParent(b,i) && !isParent(c,i)){
				if(isParent(i,b)){
					ans[i] = sz[c]*(sz[b]-sz[i]);
					b = i;
				}
				else if(isParent(i,c)){
					ans[i] = sz[b]*(sz[c]-sz[i]);
					c = i;
				}
				else{
					ans[n] = 0;
					ans[i] = sz[c]*sz[b];
					break;
				}
			}
		}
	}
	for(ll i=0;i<=n;i++){
		cout << ans[i] << " ";
	}
	cout << endl;
	for(ll i=0;i<n;i++){
		g[i].clear();
		sz[i] = 0;
		col[i] =0;
		vis[i] = false;
		ans[i] = 0;
		vt[i] = 0;
		lt[i] = 0;
		d[i] = 0;
		timer = 0;	
	}
}

int main(){
	//freopen("input.txt","r",stdin);
	//freopen("output.txt","w",stdout);
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int tc;
	tc = 1;
	cin >> tc;
	for(int i=1;i<=tc;i++){
		//cout << "Case #" << i << ": ";
		solve();
	}
	return 0;
}

```