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:
// Problem ID - 1527D

#include <vector>
#define debug(...)
#include <bits/stdc++.h>
using namespace std;
void solve();

#define ll long long

const int MAX_N = 200001;
const int MOD = 1000*1000*1000 + 7;
const int INF = 1000*1000*1000;
const ll LINF = 1ll*1000000*1000000*1000000;

int main() {

	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int t=1;
	/*is Single Test case?*/cin >> t;
	for (int i = 0; i < t; ++i) {
		solve();
		cout << "\n";
	}

	cerr << "time taken : " << (float)clock()/CLOCKS_PER_SEC << " secs" << "\n";
	return 0;
}



void solve() {

	ll n; cin >> n;

	vector<ll> adj[n+1];
	vector<ll> children(n+1, 0);

	vector<ll> parent(n+1, 0);

	function<void(ll,ll)> dfs;

	dfs = [&] (ll u, ll par){

		children[u] = 1;
		parent[u] = par;

		for (auto v: adj[u]){
			if (v != par){
				dfs(v, u);
				children[u] += children[v];
			}
		}
	};

	for (ll i = 0; i < n-1; ++i){
		ll u, v; cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}

	dfs(0, -1);

	ll endpt1 = 0, endpt2 = 0;

	vector<ll> covered(n, 0);
	covered[0] = 1;
	vector<ll> ans(n, 0);

	ll note1 = -1;
	ll note = -1;

	ll i = 1;
	for (; i < n; ++i){
		if (covered[i]){
			ans[i] = 0;
			continue;
		}

		ll j = i;

		while (!covered[j]){
			covered[j] = 1;
			if (parent[j] == 0) note = j;
			if (parent[j] == 0 and i == 1) note1 = note;
			debug(j);
			j = parent[j];
		}
		

		debug(endpt1, endpt2, note);		
		if (j != endpt1 and j != endpt2){
			covered[i] = 0;
			break;
		}

		if (endpt1 != 0 and endpt2 != 0){
			if (j == endpt1)
				ans[i] = (children[j] - children[i])*children[endpt2];
			else
				ans[i] = (children[j] - children[i])*children[endpt1];
		}

		else if (endpt1 != 0 or endpt2 != 0){
			if (j != 0){
				ans[i] = (children[j] - children[i])*(n - children[note]); 
			}

			else{
				ll k = endpt1 == 0? endpt2: endpt1;
				ll temp = -1;
				for (auto next: adj[0]){
					if (next != note and covered[next])
						temp = next;
				}

				ans[i] = children[k] * (n - children[i] - children[temp]);
			}
		}

		else {

		}

		j == endpt1? endpt1 = i: endpt2 = i;

	}

	// debug(children);
	for (auto next: adj[0]){
		ans[0] += children[next]*(children[next] - 1) / 2;
	}

	debug(note1);
	ll sum = 0;
	ll temp = children[1];
	children[note1] -= children[1];

	ll sum2 = 0;
	for (auto next: adj[0]){
		sum += children[next];
		sum2 += children[next]*children[next];
	}

	debug(sum, sum2, sum);

	ans[1] = (sum*sum - sum2)/2 + sum;

	children[note1] += temp;

	if (i < n){
		debug(endpt1, endpt2, note);
		if (endpt1 != 0 and endpt2 != 0)
			ans[i] = children[endpt1]*children[endpt2];
		else{
			ll k = endpt1 == 0? endpt2: endpt1;
			debug(k, children[k], children[note]);
			ans[i] = children[k]*(n - children[note]);
		}
	}

	for (auto a: ans){
		cout << a << " ";
	}

	for (auto c: covered){
		if (c == 0){
			cout << 0;
			return;
		}
	}

	cout << 1;


}