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.util.*;
import java.io.*;
public class EdA {
	static long[] mods = {1000000007, 998244353, 1000000009};
	static long mod = mods[0];
	public static MyScanner sc;
	static ArrayList<ArrayList<Integer>> graph;
	static int[] minSubtree;
	static int[] numSubtree;
    public static PrintWriter out;
	public static void main(String[] havish) throws Exception{
		// TODO Auto-generated method stub
 		sc = new MyScanner();
 		out = new PrintWriter(System.out);
 		int t = sc.nextInt();
 		while(t-->0) {
 			int n = sc.nextInt();
 			graph = new ArrayList<>();
 			for(int j = 0;j<n;j++)
 				graph.add(new ArrayList<Integer>());
 			minSubtree = new int[n];
 			numSubtree = new int[n];
 			Arrays.fill(minSubtree,  Integer.MAX_VALUE);
 			for(int j =0 ;j<n-1;j++){
 				int v1 = sc.nextInt();
 				int v2 = sc.nextInt();
 				graph.get(v1).add(v2);
 				graph.get(v2).add(v1);
 			}
 			dfs(0, -1);
 			long term = 1;
 			long[] numMoreI = new long[n]; //ith is number of paths that include 0, 1, ..., i
 			Set<Integer> currPath = new HashSet<>();
 			int firstVal = -1;
 			currPath.add(0);
 			numMoreI[0] = (long)n*(n-1)/2;
 			for(int j : graph.get(0))
 				numMoreI[0] -= (long)numSubtree[j]*(numSubtree[j]-1)/2;
 			ArrayList<Integer> endpoints = new ArrayList<>();
 			endpoints.add(0);
 			endpoints.add(0);
 			for(int j = 1;j<n;j++){
 				boolean found = false;
 				if (currPath.contains(j)) {
 					numMoreI[j] = numMoreI[j-1];
 					continue;
 				}
 				for (int st = 0;st < endpoints.size();st++){
 					int k = endpoints.get(st);
 					for(int s : graph.get(k)){
 						if (currPath.contains(s))
 							continue;
 						if (minSubtree[s] == j){
 							currPath.add(s);
 							if (firstVal == -1)
 								firstVal = s;
 							int val = s;
 							while (val != j){
 								for(int childs : graph.get(val)) {
 									if (currPath.contains(childs))
 										continue;
 									if (minSubtree[childs] == j) {
 										val = childs;
 										break;
 									}
 									
 								}
 								currPath.add(val);
 							}						
 							endpoints.set(st,  j);						
 							found = true;
 							break;
 							
 						}
 					}
 					if (found)
 						break;
 					
 				}
 				if (!found)
 					break;
 				numMoreI[j] = term*(endpoints.get(0) == 0 ? (n - numSubtree[firstVal]) : numSubtree[endpoints.get(0)])*(endpoints.get(1) == 0 ? (n - numSubtree[firstVal]) : numSubtree[endpoints.get(1)]);
 			}
 			out.print(((long)n*(n-1)/2 - numMoreI[0]) + " ");
 			for(int j = 1;j<=n;j++){
 				out.print((numMoreI[j-1] - (j == n ? 0 : numMoreI[j])) + " ");
 			}
 			out.println();
 			
 		}
 		
 		out.close();
 		
 	}
	public static void dfs(int v, int p) {
		for(int child : graph.get(v)){
			if (child == p)
				continue;
			dfs(child, v);
			numSubtree[v] += numSubtree[child];
			minSubtree[v] = Math.min(minSubtree[v],  minSubtree[child]);
		}
		numSubtree[v] += 1;
		minSubtree[v] = Math.min(minSubtree[v],  v);
	}
	public static void sort(int[] array){
		ArrayList<Integer> copy = new ArrayList<>();
		for (int i : array)
			copy.add(i);
		Collections.sort(copy);
		for(int i = 0;i<array.length;i++)
			array[i] = copy.get(i);
	}
	static String[] readArrayString(int n){
		String[] array = new String[n];
		for(int j =0 ;j<n;j++)
			array[j] = sc.next();
		return array;
	}
	static int[] readArrayInt(int n){
    	int[] array = new int[n];
    	for(int j = 0;j<n;j++)
    		array[j] = sc.nextInt();
    	return array;
    }
	static int[] readArrayInt1(int n){
		int[] array = new int[n+1];
		for(int j = 1;j<=n;j++){
			array[j] = sc.nextInt();
		}
		return array;
	}
	static long[] readArrayLong(int n){
		long[] array = new long[n];
		for(int j =0 ;j<n;j++)
			array[j] = sc.nextLong();
		return array;
	}
	static double[] readArrayDouble(int n){
		double[] array = new double[n];
		for(int j =0 ;j<n;j++)
			array[j] = sc.nextDouble();
		return array;
	}
	static int minIndex(int[] array){
		int minValue = Integer.MAX_VALUE;
		int minIndex = -1;
		for(int j = 0;j<array.length;j++){
			if (array[j] < minValue){
				minValue = array[j];
				minIndex = j;
			}
		}
		return minIndex;
	}
	static int minIndex(long[] array){
		long minValue = Long.MAX_VALUE;
		int minIndex = -1;
		for(int j = 0;j<array.length;j++){
			if (array[j] < minValue){
				minValue = array[j];
				minIndex = j;
			}
		}
		return minIndex;
	}
	static int minIndex(double[] array){
		double minValue = Double.MAX_VALUE;
		int minIndex = -1;
		for(int j = 0;j<array.length;j++){
			if (array[j] < minValue){
				minValue = array[j];
				minIndex = j;
			}
		}
		return minIndex;
	}
	static long power(long x, long y){
		if (y == 0)
			return 1;
		if (y%2 == 1)
			return (x*power(x, y-1))%mod;
		return power((x*x)%mod, y/2)%mod;
	}
	static void verdict(boolean a){
        out.println(a ? "YES" : "NO");
    }
    public static class MyScanner {
        BufferedReader br;
        StringTokenizer st;
        public MyScanner() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }
        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } 
                catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }
        int nextInt() {
            return Integer.parseInt(next());
        }
        long nextLong() {
            return Long.parseLong(next());
        }
        double nextDouble() {
            return Double.parseDouble(next());
        }
        String nextLine() {
            String str = "";
            try{
                str = br.readLine();
            } 
            catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
        
    }	
}

//StringJoiner sj = new StringJoiner(" "); 
//sj.add(strings)
//sj.toString() gives string of those stuff w spaces or whatever that sequence is