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:
import java.io.*;
import java.util.*;

public class Main{
	static LinkedList<Integer>[]adj;
	static int[]size,tin,tout,sub;
	static int time;
	static void dfs(int i,int p,int s) {
		size[i]=1;
		tin[i]=++time;
		sub[i]=s;
		for(int j:adj[i]) {
			if(j==p)continue;
			dfs(j, i,s);
			size[i]+=size[j];
		}
		tout[i]=time;
	}
	static boolean xinSubTreeOfy(int x,int y) {
		return tin[y]<=tin[x] && tout[x]<=tout[y];
	}
	static void main() throws Exception{
		int n=sc.nextInt();
		adj=new LinkedList[n];
		for(int i=0;i<n;i++)adj[i]=new LinkedList<Integer>();
		for(int i=0;i<n-1;i++) {
			int x=sc.nextInt(),y=sc.nextInt();
			adj[x].add(y);
			adj[y].add(x);
		}
		int root1=1;
		size=new int[n];
		tin=new int[n];
		tout=new int[n];
		sub=new int[n];
		time=0;
		long[]ans=new long[n+1];
		size[0]=1;
		for(int j:adj[0]) {
			dfs(j, 0, j);
			size[0]+=size[j];
			long cur=size[j];
			ans[0]+=(cur)*(cur-1)/2;
		}
		tout[0]=time;
		long all=1;
		for(int j:adj[0]) {
			if(j==sub[1])continue;
			ans[1]+=all*size[j];
			all+=size[j];
		}
		ans[1]+=all*(size[sub[1]]-size[1]);
		int mex=1;
		mex++;
		int root2=-1;
		for(;mex<=n;mex++) {
			if(mex==n) {
				ans[n]=1;
				break;
			}
			if(xinSubTreeOfy(mex, root1)) {
				ans[mex]=all*(size[root1]-size[mex]);
				root1=mex;
				continue;
			}
			if(xinSubTreeOfy(root1, mex)) {
				continue;
			}
//			System.out.println(mex+" "+all);
			if(sub[mex]!=sub[1])
				all-=size[mex];
			ans[mex]=all*size[root1];
			root2=mex++;
			break;
			
		}
		if(root2==-1 || (sub[root2]==sub[root1]))mex=n+7;
		for(;mex<=n;mex++) {
			if(mex==n) {
				ans[n]=1;
				break;
			}
			if(xinSubTreeOfy(mex, root1)) {
				ans[mex]=size[root2]*(size[root1]-size[mex]);
				root1=mex;
				continue;
			}
			if(xinSubTreeOfy(mex, root2)) {
				ans[mex]=size[root1]*(size[root2]-size[mex]);
				root2=mex;
				continue;
			}
			if(xinSubTreeOfy(root1, mex) || xinSubTreeOfy(root2, mex)) {
				continue;
			}
			ans[mex]=size[root1]*size[root2];
			break;
		}
		
		for(int i=0;i<=n;i++)pw.print(ans[i]+" ");
		pw.println();
	}
	public static void main(String[] args) throws Exception{
		sc=new MScanner(System.in);
		pw = new PrintWriter(System.out);
		int tc=1;
        tc=sc.nextInt();
		for(int i=1;i<=tc;i++) {
//			pw.printf("Case #%d: ", i);
			main();
		}
		
		pw.flush();
	}
	static PrintWriter pw;
	static MScanner sc;
	static class MScanner {
		StringTokenizer st;
		BufferedReader br;
		public MScanner(InputStream system) {
			br = new BufferedReader(new InputStreamReader(system));
		}
	 
		public MScanner(String file) throws Exception {
			br = new BufferedReader(new FileReader(file));
		}
	 
		public String next() throws IOException {
			while (st == null || !st.hasMoreTokens())
				st = new StringTokenizer(br.readLine());
			return st.nextToken();
		}
		public int[] intArr(int n) throws IOException {
	        int[]in=new int[n];for(int i=0;i<n;i++)in[i]=nextInt();
	        return in;
		}
		public long[] longArr(int n) throws IOException {
	        long[]in=new long[n];for(int i=0;i<n;i++)in[i]=nextLong();
	        return in;
		}
		public int[] intSortedArr(int n) throws IOException {
	        int[]in=new int[n];for(int i=0;i<n;i++)in[i]=nextInt();
	        shuffle(in);
	        Arrays.sort(in);
	        return in;
		}
		public long[] longSortedArr(int n) throws IOException {
	        long[]in=new long[n];for(int i=0;i<n;i++)in[i]=nextLong();
	        shuffle(in);
	        Arrays.sort(in);
	        return in;
		}
		public Integer[] IntegerArr(int n) throws IOException {
	        Integer[]in=new Integer[n];for(int i=0;i<n;i++)in[i]=nextInt();
	        return in;
		}
		public Long[] LongArr(int n) throws IOException {
	        Long[]in=new Long[n];for(int i=0;i<n;i++)in[i]=nextLong();
	        return in;
		}
		public String nextLine() throws IOException {
			return br.readLine();
		}
	 
		public int nextInt() throws IOException {
			return Integer.parseInt(next());
		}
	 
		public double nextDouble() throws IOException {
			return Double.parseDouble(next());
		}
	 
		public char nextChar() throws IOException {
			return next().charAt(0);
		}
	 
		public long nextLong() throws IOException {
			return Long.parseLong(next());
		}
	 
		public boolean ready() throws IOException {
			return br.ready();
		}
	 
		public void waitForInput() throws InterruptedException {
			Thread.sleep(3000);
		}
		
	}
	static void shuffle(int[]in) {
		for(int i=0;i<in.length;i++) {
			int idx=(int)(Math.random()*in.length);
			int tmp=in[i];
			in[i]=in[idx];
			in[idx]=tmp;
		}
	}
	static void shuffle(long[]in) {
		for(int i=0;i<in.length;i++) {
			int idx=(int)(Math.random()*in.length);
			long tmp=in[i];
			in[i]=in[idx];
			in[idx]=tmp;
		}
	}
}