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>
#include<string.h>
#define int long long
#include<vector>
#define rep(i,a,b)        for(int i=a;i<b;i++)
#define pb                push_back
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
const int N=2e5+5;
 
vector<int> v[N];
int siz[N];
int lvl[N];
 
int forefather[N];
 
int tim = 0, st[N], et[N];
 
void dfs(int z,int p = -1,int ff = 0){
	if(p == -1) lvl[z] = 0;
	else lvl[z] = lvl[p] + 1;
	
	if(lvl[z] == 1) ff = z;
	forefather[z] = ff;
	
	st[z] = tim++;
	
	siz[z] = 1;
	for(int x:v[z]){
		if(x == p) continue;
		dfs(x,z,ff);
		siz[z] += siz[x];
	}
	et[z] = tim;
}
 
// x is ancestor of y
bool ancestor(int x,int y){
	if(st[y] > st[x] && et[y] <= et[x]){
		return true;
	}
	return false;
}
 
int calc(int x,int y){
	if(y == 0) swap(x,y);
	if(x == 0){
		return siz[y] * (siz[0] - siz[forefather[y]]);
	}
	return siz[x] * siz[y];
}
 
void solve(){
	tim = 0;
	int n;
	cin >> n;
	rep(i,0,n){
		v[i].clear();
		siz[i] = 0;
		lvl[i] = 0;
		forefather[i] = 0;
	}
	rep(i,1,n){
		int x,y;
		cin >> x >> y;
		v[x].pb(y);
		v[y].pb(x);
	}
	
	dfs(0);
	
	int paths = n * (n - 1) / 2;
	int donthavezero = 0;
	rep(i,1,n){
		if(lvl[i] != 1) continue;
		donthavezero += siz[i] * (siz[i] - 1) / 2;
	}
	cout << donthavezero << " ";
	paths -= donthavezero;
	
	int a = 0, b = 0;
	
	rep(i,1,n){
		if(paths == 0){
			cout << 0 << " ";
			continue;
		}
		if(a == 0) swap(a,b);
		if(ancestor(i,a) || ancestor(i,b)){
			cout << 0 << " ";
			continue;
		}
		if(ancestor(a,i)){
			a = i;
			int wont_work = calc(a,b);
			cout << paths - wont_work << " ";
			paths = wont_work;
		}
		else if(ancestor(b,i)){
			if(forefather[i] == forefather[a]){
				cout << paths << " ";
				paths = 0;
				continue;
			}
			b = i;
			int wont_work = calc(a,b);
			cout << paths - wont_work << " ";
			paths = wont_work;
		}
		else{
			cout << paths << " ";
			paths = 0;
		}
	}
	
	cout << paths;
	
	cout << "\n";
}
signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	
	int t=1;
	cin>>t;
	while(t--) solve();
	return 0;
}