#include<bits/stdc++.h>
using namespace std;
# define ll long long
# define read read1<ll>()
# define Type template<typename T>
Type T read1(){
	T t=0;
	char k;
	bool vis=0;
	do (k=getchar())=='-'&&(vis=1);while('0'>k||k>'9');
	while('0'<=k&&k<='9')t=(t<<3)+(t<<1)+(k^'0'),k=getchar();
	return vis?-t:t;
}
# define fre(k) freopen(k".in","r",stdin);freopen(k".out","w",stdout)
int fa[200005],s,sz[200005],sta[200005],to[200005];
ll ans[200005];
bool vis[200005];
vector<int>G[200005];
void dfs(int n,int f){
	fa[n]=f;sz[n]=1;
	while(*sta&&sta[*sta]>n)vis[sta[*sta]]=1,--*sta;
	to[n]=sta[*sta];sta[++*sta]=n;
	for(auto i:G[n])
		if(i!=f)dfs(i,n),sz[n]+=sz[i];
	if(sta[*sta]==n)--*sta;
}
void Put(ll x){
	static int st[20],p;
	if(x<0)putchar('-'),x=-x;
	do st[++p]=x-x/10*10,x/=10;while(x);
	while(p)putchar(st[p]^'0'),--p;
}
int main(){
	for(int T=read;T--;){
		s=read;*sta=0;memset(vis,0,s);
		for(int i=0;i<s;++i)G[i].clear();
		for(int i=1;i<s;++i){
			int u=read,v=read;
			G[u].push_back(v);
			G[v].push_back(u);
		}dfs(0,0);ans[0]=ans[s]=0;
		int u=0,v=0,lt=-1,t=1,p=0;
		for(auto i:G[0])ans[0]+=1ll*t*sz[i],t+=sz[i];
		for(int i=1;i<s;++i){
			if(vis[i]){ans[i]=ans[i-1];continue;}
			if(to[i]==v)swap(u,v);
			if(to[i]==u){
				if(!u&&v){
					int j=i;while(fa[j])j=fa[j];
					if(j==p){memset(ans+i,0,s-i+1<<3);break;}
				}
				u=i;
				if(!v)
					if(~lt)ans[i]=1ll*sz[u]*lt;
					else{
						int j=u;lt=1;while(fa[j])j=fa[j];
						for(auto x:G[0])if(x!=j)lt+=sz[x];
						ans[i]=1ll*sz[u]*lt;p=j;
					}
				else ans[i]=1ll*sz[u]*sz[v];
			}else{memset(ans+i,0,s-i+1<<3);break;}
		}Put(1ll*s*(s-1)/2-ans[0]);putchar(' ');
		for(int i=0;i<s;++i)Put(ans[i]-ans[i+1]),putchar(' ');;putchar('\n');
	}
	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 ll long long
# define read read1<ll>()
# define Type template<typename T>
Type T read1(){
	T t=0;
	char k;
	bool vis=0;
	do (k=getchar())=='-'&&(vis=1);while('0'>k||k>'9');
	while('0'<=k&&k<='9')t=(t<<3)+(t<<1)+(k^'0'),k=getchar();
	return vis?-t:t;
}
# define fre(k) freopen(k".in","r",stdin);freopen(k".out","w",stdout)
int fa[200005],s,sz[200005],sta[200005],to[200005];
ll ans[200005];
bool vis[200005];
vector<int>G[200005];
void dfs(int n,int f){
	fa[n]=f;sz[n]=1;
	while(*sta&&sta[*sta]>n)vis[sta[*sta]]=1,--*sta;
	to[n]=sta[*sta];sta[++*sta]=n;
	for(auto i:G[n])
		if(i!=f)dfs(i,n),sz[n]+=sz[i];
	if(sta[*sta]==n)--*sta;
}
void Put(ll x){
	static int st[20],p;
	if(x<0)putchar('-'),x=-x;
	do st[++p]=x-x/10*10,x/=10;while(x);
	while(p)putchar(st[p]^'0'),--p;
}
int main(){
	for(int T=read;T--;){
		s=read;*sta=0;memset(vis,0,s);
		for(int i=0;i<s;++i)G[i].clear();
		for(int i=1;i<s;++i){
			int u=read,v=read;
			G[u].push_back(v);
			G[v].push_back(u);
		}dfs(0,0);ans[0]=ans[s]=0;
		int u=0,v=0,lt=-1,t=1,p=0;
		for(auto i:G[0])ans[0]+=1ll*t*sz[i],t+=sz[i];
		for(int i=1;i<s;++i){
			if(vis[i]){ans[i]=ans[i-1];continue;}
			if(to[i]==v)swap(u,v);
			if(to[i]==u){
				if(!u&&v){
					int j=i;while(fa[j])j=fa[j];
					if(j==p){memset(ans+i,0,s-i+1<<3);break;}
				}
				u=i;
				if(!v)
					if(~lt)ans[i]=1ll*sz[u]*lt;
					else{
						int j=u;lt=1;while(fa[j])j=fa[j];
						for(auto x:G[0])if(x!=j)lt+=sz[x];
						ans[i]=1ll*sz[u]*lt;p=j;
					}
				else ans[i]=1ll*sz[u]*sz[v];
			}else{memset(ans+i,0,s-i+1<<3);break;}
		}Put(1ll*s*(s-1)/2-ans[0]);putchar(' ');
		for(int i=0;i<s;++i)Put(ans[i]-ans[i+1]),putchar(' ');;putchar('\n');
	}
	return 0;
}
```