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;

#define rep(i,_l,_r) for(signed i=(_l),_end=(_r);i<=_end;++i)
#define fep(i,_l,_r) for(signed i=(_l),_end=(_r);i>=_end;--i)
#define erep(i,u) for(signed i=head[u],v=to[i];i;i=nxt[i],v=to[i])
#define efep(i,u) for(signed i=Head[u],v=to[i];i;i=nxt[i],v=to[i])
#define print(x,y) write(x),putchar(y) 
#define debug(...) do {cerr<<__LINE__<<" : ("#__VA_ARGS__<<") = "; Out(__VA_ARGS__); cerr<<flush;} while(0)
template <typename T> void Out(T x) {cerr<<x<<"\n";}
template <typename T,typename ...I> void Out(T x,I ...NEXT) {cerr<<x<<", "; Out(NEXT...);}

template <class T> inline T read(const T sample) {
    T x=0; int f=1; char s;
    while((s=getchar())>'9'||s<'0') if(s=='-') f=-1;
    while(s>='0'&&s<='9') x=(x<<1)+(x<<3)+(s^48),s=getchar();
    return x*f;
}
template <class T> inline void write(const T x) {
    if(x<0) return (void) (putchar('-'),write(-x));
    if(x>9) write(x/10);
    putchar(x%10^48);
}
template <class T> inline T Max(const T x,const T y) {if(x>y) return x; return y;}
template <class T> inline T Min(const T x,const T y) {if(x<y) return x; return y;}
template <class T> inline T fab(const T x) {return x>0?x:-x;}
template <class T> inline T gcd(const T x,const T y) {return y?gcd(y,x%y):x;}
template <class T> inline T lcm(const T x,const T y) {return x/gcd(x,y)*y;}
template <class T> inline T Swap(T &x,T &y) {x^=y^=x^=y;}

typedef long long ll;
#define int long long

const int maxn=2e5+5;

int n,l,r;
vector <int> e[maxn];
bool flag;
ll ans[maxn],ans1;
int siz[maxn],f[maxn][20],dep[maxn];

void dfs(int u,int fa) {
	f[u][0]=fa,dep[u]=dep[fa]+1,siz[u]=1;
	rep(i,1,18) f[u][i]=f[f[u][i-1]][i-1];
	for(int i=0;i<e[u].size();++i) {
		int v=e[u][i];
		if(v==fa) continue;
		dfs(v,u);
		if(u==1) ans1+=1ll*siz[1]*siz[v];
		siz[u]+=siz[v]; 
	}
}

int Lca(int x,int y) {
	if(dep[x]<dep[y]) swap(x,y);
	fep(i,18,0) if(dep[f[x][i]]>=dep[y]) x=f[x][i];
	if(x==y) return x;
	fep(i,18,0) if(f[x][i]^f[y][i]) x=f[x][i],y=f[y][i];
	return f[x][0];
}

int jump(int x) {
	fep(i,18,0) if(dep[f[x][i]]>dep[1]) x=f[x][i];
	return x;
}

ll calc() {
	if(!flag) return 0; 
	if(l>r) swap(l,r);
	if(l==1 && r==1) return ans1;
	if(l==1) {
		int Son=jump(r);
		return 1ll*siz[r]*(n-siz[Son]);
	}
	return 1ll*siz[l]*siz[r];
}

void ins(int i) {
	if(!flag) return;
	if(l>r) swap(l,r);
	int l1=Lca(l,i),l2=Lca(r,i);
	if(l==1 && r==1) r=i;
	else if(l==1) {
		if(l2==r) r=i;
		else if(l2==1) l=i;
		else if(l2^i) flag=false;
	}
	else {
		if(l1==l) l=i;
		else if(l2==r) r=i;
		else if(!(l1==i || l2==i)) flag=false;
	}
}

signed main() {
	rep(T,1,read(9)) {
		n=read(9); l=r=flag=1,ans1=0;
		rep(i,1,n) e[i].clear();
		rep(i,1,n-1) {
			int u=read(9)+1,v=read(9)+1;
			e[u].push_back(v),e[v].push_back(u);
		}
		dfs(1,0); ans[1]=1ll*n*(n-1)/2; 
		rep(i,2,n) {
			ans[i]=calc(); //debug(i,l,r,ans[i]);
			ins(i);
		}
		ans[n+1]=calc(),ans[n+2]=0;
		//debug(n+1,l,r,ans[n+1]);
		rep(i,1,n+1) print(ans[i]-ans[i+1],' '); puts("");
	}
	return 0;
} 
/*
1
3
1 0
2 1

*/