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 <iostream>
#include <cmath>
#include <utility>
#include <vector>

using namespace std;

#define mp make_pair
#define x first
#define y second
typedef pair<int,int> pii;
typedef long long ll;

ll siz[200005],depth[200005],sol[200005];
int anc[20][200005],st[200005],en[200005],cnt;
vector<int> veki[200005];

ll dfs(int x,int p){
	depth[x]=depth[p]+1ll;
	cnt++;
	st[x]=cnt;
	siz[x]=1ll;
	anc[0][x]=p;
	for(int i=0;i<veki[x].size();i++){
		int v=veki[x][i];
		if(p==v) continue;
		siz[x]+=dfs(v,x);
	}
	cnt++;
	en[x]=cnt;
	return siz[x];
}

void lca_prep(ll n){
	for(int i=1;i<19;i++){
		for(int j=1;j<=n;j++){
			anc[i][j]=anc[i-1][anc[i-1][j]];
		}
	}
}
int getanc(int x,int k){
	for(int i=0;i<19;i++){
		if((k&(1<<i))) x=anc[i][x];
	}
	return x;
}
int lca(int x,int y){
	if(depth[x]<depth[y]) swap(x,y);
	x=getanc(x,depth[x]-depth[y]);
	if(x==y) return x;
	for(int i=18;i>=0;i--){
		if(anc[i][x]!=anc[i][y]){
			x=anc[i][x];
			y=anc[i][y];
		}
	}
	return anc[0][x];
}
int check(int x,int y){
	if(st[x]>=st[y] and en[x]<=en[y]) return 1;
	return 0;
}


int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int t;
	cin>>t;
	while(t--){
		ll n;
		cin>>n;
		for(int i=1;i<n;i++){
			int a,b;
			cin>>a>>b;
			veki[a+1].push_back(b+1);
			veki[b+1].push_back(a+1);
		}
		sol[0]=n*(n-1ll)/2ll;
		dfs(1,0);
		lca_prep(n);
		ll add=0ll;
		for(int i=0;i<veki[1].size();i++){
			add+=siz[veki[1][i]]*(siz[veki[1][i]]-1ll)/2ll;
		}
		sol[1]=sol[0]-add;
		int k1=1,k2=2;
		for(int i=2;i<=n;i++){
			int l=lca(k1,k2);
			if(l==k1 or l==k2){
				if(depth[k1]>depth[k2]) swap(k1,k2);
				int fc=getanc(k2,depth[k2]-depth[k1]-1);
				sol[i]=siz[k2]*(siz[k1]-siz[fc]);
			}
			else{
				sol[i]=siz[k1]*siz[k2];
			}
			int nd=i+1;
			if(l!=k1 and l!=k2){
				if(check(nd,l)){
					if(check(nd,k1)) k1=nd;
					else if(check(nd,k2)) k2=nd;
					else if(check(k1,nd) or check(k2,nd)) continue;
					else break;
				}
				else break;
			}
			else{
				if(check(nd,k2)) k2=nd;
				else if(check(k2,nd)) continue;
				else if(lca(nd,k2)==k1) k1=nd;
				else break;
			}
		}
		for(int i=1;i<=n+1;i++){
			cout<<sol[i-1]-sol[i]<<" ";
		}
		cout<<"\n";
		for(int i=1;i<=n;i++){
			for(int j=0;j<19;j++) anc[j][i]=0;
			sol[i]=depth[i]=siz[i]=st[i]=en[i]=0;
			veki[i].clear();
		}
	}




return 0;
}