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. 

Solution (in CPP):

Solution:
#include<bits/stdc++.h>
using namespace std;
inline int read()
{
	int x=0,f=1;char c=getchar();
	while(c<'0'||c>'9') {if(c=='-') f=-1;c=getchar();}
	while (c>='0'&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();
	return x*f;
}

const int maxn=2e5+100;
int t,n;
int sz[maxn]; 
int dfn[maxn];
int tot=0;
vector<int> g[maxn];
int father[30][maxn];
int h[maxn];
void dfs (int x,int pre) {
	sz[x]=1;
	dfn[x]=++tot;
	for (int y:g[x]) {
		if (y==pre) continue;
		h[y]=h[x]+1;
		father[0][y]=x;
		dfs(y,x);
		sz[x]+=sz[y];
	}
}
int lca (int x,int y) {
	if (h[x]<h[y]) swap(x,y);
	for (int i=20;i>=0;i--) {
		if (h[x]-h[y]>>i) x=father[i][x];
	}
	if (x==y) return x;
	for (int i=20;i>=0;i--) {
		if (father[i][x]!=father[i][y]) {
			x=father[i][x];
			y=father[i][y];
		}
	}
	return father[0][x];
}
int main ()  {
	t=read();
	while (t--) {
		n=read();
		tot=0;
		for (int i=0;i<=20;i++) for (int j=0;j<n;j++) father[i][j]=0;
		for (int i=0;i<n;i++) g[i].clear(),h[i]=0;
		for (int i=1;i<n;i++) {
			int x=read();
			int y=read();
			g[x].push_back(y);
			g[y].push_back(x);
		}
		dfs(0,-1);
		for (int i=1;i<=20;i++) for (int j=0;j<n;j++) father[i][j]=father[i-1][father[i-1][j]];
		//容斥计算0的答案
		//就是0的所有子树内部算一下路径即可
		long long ans=0;
		for (int y:g[0]) {
			ans+=1ll*sz[y]*(sz[y]-1)/2;
		} 
		printf("%lld ",ans);
		//容斥计算1的答案
		//就是所有经过0的路径减去经过01的路径
		//1子树内的点不考虑即可 
		ans=0;
		long long sum=1;
		int fa=-1;
		for (int y:g[0]) {
			int x=sz[y];
			if (dfn[1]>=dfn[y]&&dfn[1]<=dfn[y]+sz[y]-1) {
				//如果1在y的子树内
				fa=y;
				x-=sz[1]; 
			}
			ans+=1ll*x*sum;
			sum+=x;
		}
		printf("%lld ",ans);
		int A=0,B=1;//AB分别表示之前路径的起点和终点
		//fa表示如果A为0，B在A的哪个子树 
		for (int i=2;i<=n;i++) {
			//计算mex=i的答案
			//如果i==n
			if (i==n) {
				printf("1 ");
				break;
			} 
			
			
			//先讨论i的位置
			//i在B的子树内
			if (dfn[i]>=dfn[B]&&dfn[i]<=dfn[B]+sz[B]-1) {
				ans=0;
				long long x,y;
				if (A==0) {
					x=n-sz[fa];
				}
				else {
					x=sz[A];
				}
				y=sz[B]-sz[i];
				ans=1ll*x*y;
				printf("%lld ",ans);
				B=i;
			} 
			else {
				//如果i在A的子树内
				if (A==0&&(dfn[i]<dfn[fa]||dfn[i]>dfn[fa]+sz[fa]-1)) {
					ans=0;
					long long x,y;
					x=n-sz[fa]-sz[i];
					y=sz[B];
					ans=1ll*x*y;
					printf("%lld ",ans);
					A=i;
				} 
				else if (A!=0&&dfn[i]>=dfn[A]&&dfn[i]<=dfn[A]+sz[A]-1) {
					ans=0;
					long long x,y;
					x=sz[A]-sz[i];
					y=sz[B];
					ans=1ll*x*y;
					printf("%lld ",ans);
					A=i;
				}
				//如果i在A到B的路径上
				//答案是0 
				else if (lca(A,i)==i||lca(B,i)==i) {
					ans=0;
					printf("%lld ",ans);
				}
				//如果不在 
				//答案是包含A到B的路径的路径数量
				// 
				else {
					long long x,y;
					ans=0;
					if (A==0) x=n-sz[fa];
					else x=sz[A];
					y=sz[B];
					ans=1ll*x*y;
					printf("%lld ",ans);
					for (int j=i+1;j<=n;j++) printf("0 ");
					break;
				}
			}
		}
		printf("\n");
	}
}