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 JAVA):

Solution:
//Implemented By Aman Kotiyal Date:-21-May-2021  Time:-8:18:07 pm
import java.io.*;
import java.util.*;

public class ques5
{
	public static void main(String[] args)throws Exception{ new ques5().run();} 
	long mod=1000000000+7;
	ArrayList<Integer> adj[];
	int N;
	long subs[];
	int fa[];
	void init(int N)
	{
		adj=new ArrayList[N+1];
		subs=new long[N+1];
		fa=new int[N+1];
		Arrays.fill(subs, 1);
		for (int i = 0; i < adj.length; i++) 
			adj[i]=new ArrayList<>();
	}
	void solve() throws Exception
	{
		for(int ii=ni();ii>0;ii--)
		{
			int n=ni();
			init(n);
			for(int i=0;i<n-1;i++)
			{
				int u=ni();
				int v=ni();
				adj[u].add(v);
				adj[v].add(u);
			}
			subs[0]=dfs(0,-1);
			long ans[]=new long[n+2];
		//	for(int u:adj[0])
		//		ans[0]+= ( subs[u]*(subs[u]-1) )/2;
		//	ans[1]=(((long)n*(long)(n-1))/2l )-(ans[0]); // MEX >= 1
		    long cnt = 1;
		    ans[0] = ((long)n * (long)(n - 1)) / 2;
		    for (int x : adj[0]) {
		      ans[1] += cnt * subs[x];
		      cnt += subs[x];
		    }
			int l=0,r=0;
			
			int vis[]=new int[n+1];
			vis[0]=1;
			for(int i=1;i<n;i++)
			{
				if(vis[i]==0) {
				int x=i,p=i;
				while(vis[x]==0)
				{
					vis[x]=1;
					p=x;
					x=fa[x];
				}
				if(x==l)
				{
					subs[x]-=subs[p];
					l=i;
				}
				else if(x==r)
				{
					subs[x]-=subs[p];
					r=i;
				}
				else 
					break;
				}
				ans[i+1]=subs[l]*subs[r];
			}
			//out.print(ans[0]+" ");	
			for(int i=0;i<=n;i++)
				out.print((ans[i]-ans[i+1])+" ");
			out.println();
		}
	}
	
	long dfs(int c, int p)
	{
		for(int u:adj[c])
		{
			if(u==p)continue;
			fa[u]=c;
			subs[c]+=dfs(u,c);
		}
		return subs[c];
	}
	/*FAST INPUT OUTPUT & METHODS BELOW*/
	
	private byte[] buf=new byte[1024];
	private int index;
	private InputStream in;
	private int total;
	private SpaceCharFilter filter;
	PrintWriter out;
	
	int min(int... ar){int min=Integer.MAX_VALUE;for(int i:ar)min=Math.min(min, i);return min;}
	long min(long... ar){long min=Long.MAX_VALUE;for(long i:ar)min=Math.min(min, i);return min;}
	int max(int... ar) {int max=Integer.MIN_VALUE;for(int i:ar)max=Math.max(max, i);return max;}
	long max(long... ar) {long max=Long.MIN_VALUE;for(long i:ar)max=Math.max(max, i);return max;}
	void reverse(int a[]){for(int i=0;i<a.length>>1;i++){int tem=a[i];a[i]=a[a.length-1-i];a[a.length-1-i]=tem;}}
	void reverse(long a[]){for(int i=0;i<a.length>>1;i++){long tem=a[i];a[i]=a[a.length-1-i];a[a.length-1-i]=tem;}}
	String reverse(String s){StringBuilder sb=new StringBuilder(s);sb.reverse();return sb.toString();}
	
	void shuffle(int a[]) {
		ArrayList<Integer> al = new ArrayList<>();
		for(int i=0;i<a.length;i++) 
			al.add(a[i]);
		
		Collections.sort(al);
		for(int i=0;i<a.length;i++) 
			a[i]=al.get(i);
	}
	long lcm(long a,long b)
	{
		return (a*b)/(gcd(a,b));
	}
	
	int gcd(int a, int b) 
	{ 
		if (a == 0) 
			return b; 
		return gcd(b%a, a); 
	} 
	long gcd(long a, long b) 
	{ 
		if (a == 0) 
			return b; 
		return gcd(b%a, a); 
	}
	/* for (1/a)%mod = ( a^(mod-2) )%mod  ----> use expo to calc -->(a^(mod-2)) */
	long expo(long p,long q)  /*  (p^q)%mod   */
	{
		long z = 1;
		while (q>0) {
			if (q%2 == 1) {
				z = (z * p)%mod;
			}
			p = (p*p)%mod;
			q >>= 1;
		}
		return z;
	}
	void run()throws Exception
	{
		in=System.in; out = new PrintWriter(System.out);
		solve();
		out.flush();
	}
	private int scan()throws IOException
	{
		if(total<0)
			throw new InputMismatchException();
		if(index>=total)
		{
			index=0;
			total=in.read(buf);
			if(total<=0)
				return -1;
		}
		return buf[index++];
	}
	private int ni() throws IOException 
	{
		int c = scan();
		while (isSpaceChar(c))
			c = scan();
		int sgn = 1;
		if (c == '-') {
			sgn = -1;
			c = scan();
		}
		int res = 0;
		do {
			if (c < '0' || c > '9')
				throw new InputMismatchException();
			res *= 10;
			res += c - '0';
			c = scan();
		} while (!isSpaceChar(c));
		return res * sgn;
	}
	private long nl() throws IOException 
	{
		long num = 0;
		int b;
		boolean minus = false;
		while ((b = scan()) != -1 && !((b >= '0' && b <= '9') || b == '-'))
			;
		if (b == '-') {
			minus = true;
			b = scan();
		}
		
		while (true) {
			if (b >= '0' && b <= '9') {
				num = num * 10 + (b - '0');
			} else {
				return minus ? -num : num;
			}
			b = scan();
		}
	}
	private double nd() throws IOException{
		return Double.parseDouble(ns());
	}
	private String ns() throws IOException {
		int c = scan();
		while (isSpaceChar(c))
			c = scan();
		StringBuilder res = new StringBuilder();
		do {
			if (Character.isValidCodePoint(c))
				res.appendCodePoint(c);
			c = scan();
		} while (!isSpaceChar(c));
		return res.toString();
	}
	private String nss() throws IOException
	{
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		return br.readLine();
	}
	private char nc() throws IOException 
	{
		int c = scan();
		while (isSpaceChar(c))
			c = scan();
		return (char) c;
	}
	private boolean isWhiteSpace(int n)
	{
		if(n==' '||n=='\n'||n=='\r'||n=='\t'||n==-1)
			return true;
		return false;
	}
	private boolean isSpaceChar(int c) {
		if (filter != null)
			return filter.isSpaceChar(c);
		return isWhiteSpace(c);
	}
	private interface SpaceCharFilter {
		public boolean isSpaceChar(int ch);
	}
}