#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define N 200100
int n;
vector<int> a[N];
int f[N];
LL siz[N];
LL ans[N];
LL outa[N];
int pathv[2];
bool vis[N];
int subcnt=0;
bool fl;
set<int> leaves;
LL tominus;
void buildtree(int i,int pre)
{
	f[i]=pre;
	siz[i]=1;
	int len=a[i].size();
	for(int j=0;j<len;++j)
	{
		int tar=a[i][j];
		if(f[i]!=tar)
		{
			buildtree(tar,i);
			siz[i]+=siz[tar];
		}
	}
}
bool work(int i)
{
	if(vis[i])return 1;
	vis[i]=1;
	int fa=f[i];
	while(!vis[fa])
	{
		vis[fa]=1;
		fa=f[fa];
	}
	bool fl=0;
	for(int j=0;j<=1;++j)
	{
		if(fa==pathv[j])
		{
			pathv[j]=i;
			fl=1;
			break;
		}
	}
	return fl;
}
LL getans(int i,int j)
{
	if(j==0)
	{
		return siz[i]*(siz[0]-siz[tominus]);
	}
	return siz[i]*siz[j];
}
int main()
{	
	ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
	int T;
	cin>>T;
	while(T--)
	{
		cin>>n;
		leaves.clear();
		subcnt=0;
		for(int i=0;i<=n;++i)a[i].clear();
		for(int i=0;i<=n;++i)ans[i]=0;
		for(int i=0;i<=n;++i)siz[i]=0;
		for(int i=1;i<=n;++i)vis[i]=0;
		for(int i=1;i<n;++i)
		{
			int u,v;
			cin>>u>>v;
			a[u].push_back(v);
			a[v].push_back(u);
		}
		buildtree(0,n+1);
		pathv[0]=pathv[1]=0;
		for(int i=1;;i=f[i])
		{
			if(f[i]==0)
			{
				tominus=i;
				break;
			}
		}
		int len=a[0].size();
		ans[0]=siz[0]*(siz[0]-1)/2;
		vis[0]=1;
		for(int i=0;i<len;++i)
		{
			int tar=a[0][i];
			ans[0]-=(siz[tar]-1)*siz[tar]/2;
		}
		for(int i=1;i<n;++i)
		{
			if(work(i))ans[i]=getans(pathv[0],pathv[1]);
			else break;
		}
		
		for(int i=0;i<n;++i)
		{
//			cout<<ans[i]<<" ";
			outa[i+1]=ans[i]-ans[i+1];
		}
//		cout<<endl;
		outa[0]=0;
		len=a[0].size();
		for(int i=0;i<len;++i)
		{
			int tar=a[0][i];
			outa[0]+=siz[tar]*(siz[tar]-1)/2;
		}
		for(int i=0;i<=n;++i)cout<<outa[i]<<" ";
		
		cout<<endl;
		
	}
}
### 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
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define N 200100
int n;
vector<int> a[N];
int f[N];
LL siz[N];
LL ans[N];
LL outa[N];
int pathv[2];
bool vis[N];
int subcnt=0;
bool fl;
set<int> leaves;
LL tominus;
void buildtree(int i,int pre)
{
	f[i]=pre;
	siz[i]=1;
	int len=a[i].size();
	for(int j=0;j<len;++j)
	{
		int tar=a[i][j];
		if(f[i]!=tar)
		{
			buildtree(tar,i);
			siz[i]+=siz[tar];
		}
	}
}
bool work(int i)
{
	if(vis[i])return 1;
	vis[i]=1;
	int fa=f[i];
	while(!vis[fa])
	{
		vis[fa]=1;
		fa=f[fa];
	}
	bool fl=0;
	for(int j=0;j<=1;++j)
	{
		if(fa==pathv[j])
		{
			pathv[j]=i;
			fl=1;
			break;
		}
	}
	return fl;
}
LL getans(int i,int j)
{
	if(j==0)
	{
		return siz[i]*(siz[0]-siz[tominus]);
	}
	return siz[i]*siz[j];
}
int main()
{	
	ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
	int T;
	cin>>T;
	while(T--)
	{
		cin>>n;
		leaves.clear();
		subcnt=0;
		for(int i=0;i<=n;++i)a[i].clear();
		for(int i=0;i<=n;++i)ans[i]=0;
		for(int i=0;i<=n;++i)siz[i]=0;
		for(int i=1;i<=n;++i)vis[i]=0;
		for(int i=1;i<n;++i)
		{
			int u,v;
			cin>>u>>v;
			a[u].push_back(v);
			a[v].push_back(u);
		}
		buildtree(0,n+1);
		pathv[0]=pathv[1]=0;
		for(int i=1;;i=f[i])
		{
			if(f[i]==0)
			{
				tominus=i;
				break;
			}
		}
		int len=a[0].size();
		ans[0]=siz[0]*(siz[0]-1)/2;
		vis[0]=1;
		for(int i=0;i<len;++i)
		{
			int tar=a[0][i];
			ans[0]-=(siz[tar]-1)*siz[tar]/2;
		}
		for(int i=1;i<n;++i)
		{
			if(work(i))ans[i]=getans(pathv[0],pathv[1]);
			else break;
		}
		
		for(int i=0;i<n;++i)
		{
//			cout<<ans[i]<<" ";
			outa[i+1]=ans[i]-ans[i+1];
		}
//		cout<<endl;
		outa[0]=0;
		len=a[0].size();
		for(int i=0;i<len;++i)
		{
			int tar=a[0][i];
			outa[0]+=siz[tar]*(siz[tar]-1)/2;
		}
		for(int i=0;i<=n;++i)cout<<outa[i]<<" ";
		
		cout<<endl;
		
	}
}
```