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>

#define int long long

using namespace std;

#ifdef LOCAL 
#include "/media/brayand/BrayanD/debugger.h"
#else
#define db(...) false
#define dbl(...) false
#define dbg(...) false
#define dbm(...) false
#define dbs(...) false
#define dbas(...) false
#endif

int32_t main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int T;
    cin >> T;

    while(T--)
    {
    	int N;
    	cin >> N;

    	vector<vector<int>> L(N);

    	for(int i = 0 ; i < N-1 ; i++)
    	{
    		int a, b;
    		cin >> a >> b;
    		L[a].push_back(b);
    		L[b].push_back(a);
    	}

    	vector<int> sz(N), la(N), lb(N), P(N), ppp(N);

    	int cont = 0;

    	vector<bool> here(N);

    	function<void(int,int)> precal = [&](int nodo, int padre)
    	{
    		sz[nodo] = 1;
    		la[nodo] = ++cont;
    		P[nodo] = padre;
    		ppp[nodo] = 1;
    		if(nodo == 1)
    		{
    			here[nodo] = true;
    		}
    		for(auto v : L[nodo])
    		{
    			if(v != padre)
    			{
    				precal(v, nodo);
    				sz[nodo] += sz[v];
    				if(v != 1)
    				{
    					ppp[nodo] += ppp[v];
    				}
    				
    				if(here[v])
    				{
    					here[nodo] = true;
    				}

    			}
    		}
    		lb[nodo] = cont;
    	};

    	precal(0,-1);

    	ppp[1] = 0;

    	auto in = [&](int a, int b)
    	{
    		if(la[a] <= la[b] && la[b] <= lb[a])return true;
    		return false;
    	};

    	vector<bool> mk(N);

    	vector<int> res(N+1);

    	vector<int> tv;

    	int sum = 0;

    	int qqq = 0;

    	for(auto v : L[0])
    	{
    		res[0] += sz[v]*(sz[v]-1)/2;
    		sum += ppp[v];
    		if(here[v])
    		{
    			qqq = v;
    		}
    	}

    	for(auto v : L[0])
    	{
    		res[1] += ppp[v]*(sum-ppp[v]);    		
    	}

    	res[1] /= 2;

    	for(auto v : L[0])
    	{
    		res[1] += ppp[v];
    	}

    	mk[0] = true;

    	int pta = 0, ptb = 0;

    	for(int i = 2 ; i <= N ; i++)
    	{
    		int pt = i-1;

    		if(!mk[pt])
    		{
	    		while(!mk[pt])
	    		{
	    			mk[pt] = true;
	    			pt = P[pt];
	    		}
	    		if(pt == pta)
	    		{
	    			pta = i-1;
	    		}
	    		else if(pt == ptb)
	    		{
	    			ptb = i-1;
	    		}
	    		else 
	    		{
	    			break;
	    		}
    		}

    		if(mk[i])continue;

    		if(ptb == 0)swap(pta, ptb);

    		if(pta == 0)
    		{
    			if(i == N)
    			{
    				res[i] += (sz[0]-sz[qqq])*(sz[ptb]);
    				continue;
    			}

    			bool b1 = in(qqq,i);
    			bool b2 = in(ptb,i);

    			if(!b1)
    			{
    				res[i] += sz[ptb]*(sz[0]-sz[qqq]-sz[i]);
    			}
    			else
    			{
    				if(b2)
    				{
    					res[i] += (sz[0]-sz[qqq])*(sz[ptb]-sz[i]);
    				}
    				else
    				{
    					res[i] += (sz[0]-sz[qqq])*(sz[ptb]);
    				}
    			}
    		}
    		else
    		{
    			if(i == N)
    			{
    				res[i] += sz[pta]*sz[ptb];
    				continue;
    			}
    			int b1 = in(pta,i);
    			int b2 = in(ptb,i);

    			if(b1)
    			{
    				res[i] += (sz[pta]-sz[i])*sz[ptb];
    			}
    			else if(b2)
    			{
    				res[i] += sz[pta]*(sz[ptb]-sz[i]);
    			}
    			else
    			{
    				res[i] += sz[pta]*sz[ptb];
    			}
    		}
    	}

    	for(auto x : res)
    	{
    		cout << x << " ";
    	}
    	cout << '\n';
    }

    return 0;
}