#include<iostream>
#include<vector>
#include<cstring>
using namespace std;
vector<int> e[200010];
int n,fa[200010][18],d[200010],size[200010];
long long ans[200010];
bool mark[200010];
void dfs(int now)
{
	for(int i=1;i<18;i++)
	{
		fa[now][i]=fa[fa[now][i-1]][i-1];
	}
	d[now]=d[fa[now][0]]+1,size[now]=1;
	for(int i=0;i<e[now].size();i++)
	{
		int t=e[now][i];
		if(t==fa[now][0])
		{
			continue;
		}
		fa[t][0]=now;
		dfs(t);
		size[now]+=size[t];
	}
}
inline bool judge(int x,int y)
{
	if(x==y)
	{
		return 1;
	}
	for(int i=17;i>=0;i--)
	{
		if(d[fa[y][i]]>d[x])
		{
			y=fa[y][i];
		}
	}
	return x==fa[y][0];
}
int main()
{
	ios::sync_with_stdio(false);
	int T;
	cin>>T;
	while(T--)
	{
		cin>>n;
		for(int i=1;i<=n;i++)
		{
			e[i].clear();
		}
		for(int i=1,x,y;i<n;i++)
		{
			cin>>x>>y;
			x++,y++;
			e[x].push_back(y);
			e[y].push_back(x);
		}
		dfs(1),memset(ans,0,sizeof(ans));
		ans[0]=(long long)n*(n-1)/2;
		for(int i=0;i<e[1].size();i++)
		{
			ans[1]+=(long long)size[e[1][i]]*(n-size[e[1][i]]-1);
		}
		ans[1]=ans[1]/2+n-1;
		memset(mark,0,sizeof(mark));
		mark[1]=1;
		for(int i=2,X=1,x=1,y=1;i<=n&&!(y==1?(!mark[i]&&judge(X,i)&&!judge(x,i)):(!mark[i]&&!judge(x,i)&&!judge(y,i)));i++)
		{
			if(i==2)
			{
				for(int j=0;j<e[1].size();j++)
				{
					if(judge(e[1][j],2))
					{
						X=e[1][j];
						break;
					}
				}
			}
			if(!mark[i])
			{
				judge(x,i)?x=i:y=i;
				int j=i;
				while(!mark[j])
				{
					mark[j]=1;
					j=fa[j][0];
				}
			}
			ans[i]=(y==1?(long long)size[x]*(n-size[X]):(long long)size[x]*size[y]);
		}
		for(int i=0;i<=n;i++)
		{
			cout<<ans[i]-ans[i+1]<<" ";
		}
		cout<<endl;
	}
	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
#include<iostream>
#include<vector>
#include<cstring>
using namespace std;
vector<int> e[200010];
int n,fa[200010][18],d[200010],size[200010];
long long ans[200010];
bool mark[200010];
void dfs(int now)
{
	for(int i=1;i<18;i++)
	{
		fa[now][i]=fa[fa[now][i-1]][i-1];
	}
	d[now]=d[fa[now][0]]+1,size[now]=1;
	for(int i=0;i<e[now].size();i++)
	{
		int t=e[now][i];
		if(t==fa[now][0])
		{
			continue;
		}
		fa[t][0]=now;
		dfs(t);
		size[now]+=size[t];
	}
}
inline bool judge(int x,int y)
{
	if(x==y)
	{
		return 1;
	}
	for(int i=17;i>=0;i--)
	{
		if(d[fa[y][i]]>d[x])
		{
			y=fa[y][i];
		}
	}
	return x==fa[y][0];
}
int main()
{
	ios::sync_with_stdio(false);
	int T;
	cin>>T;
	while(T--)
	{
		cin>>n;
		for(int i=1;i<=n;i++)
		{
			e[i].clear();
		}
		for(int i=1,x,y;i<n;i++)
		{
			cin>>x>>y;
			x++,y++;
			e[x].push_back(y);
			e[y].push_back(x);
		}
		dfs(1),memset(ans,0,sizeof(ans));
		ans[0]=(long long)n*(n-1)/2;
		for(int i=0;i<e[1].size();i++)
		{
			ans[1]+=(long long)size[e[1][i]]*(n-size[e[1][i]]-1);
		}
		ans[1]=ans[1]/2+n-1;
		memset(mark,0,sizeof(mark));
		mark[1]=1;
		for(int i=2,X=1,x=1,y=1;i<=n&&!(y==1?(!mark[i]&&judge(X,i)&&!judge(x,i)):(!mark[i]&&!judge(x,i)&&!judge(y,i)));i++)
		{
			if(i==2)
			{
				for(int j=0;j<e[1].size();j++)
				{
					if(judge(e[1][j],2))
					{
						X=e[1][j];
						break;
					}
				}
			}
			if(!mark[i])
			{
				judge(x,i)?x=i:y=i;
				int j=i;
				while(!mark[j])
				{
					mark[j]=1;
					j=fa[j][0];
				}
			}
			ans[i]=(y==1?(long long)size[x]*(n-size[X]):(long long)size[x]*size[y]);
		}
		for(int i=0;i<=n;i++)
		{
			cout<<ans[i]-ans[i+1]<<" ";
		}
		cout<<endl;
	}
	return 0;
}

```