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 D1527 {
	static ArrayList<Integer>[] adjList;
	static int[] in, out;
	static long[] subTree;
	static int counter = 0;

	public static void dfs(int u, int p) {
		in[u] = ++counter;
		subTree[u] = 1;
		for (int x : adjList[u]) {
			if (x != p) {
				dfs(x, u);
				subTree[u] += subTree[x];
			}
		}
		out[u] = counter;
	}

	public static boolean isChild(int parent, int child) {
		return in[parent] <= in[child] && in[child] <= out[parent];
	}

	public static void main(String[] args) throws IOException {
		Scanner sc = new Scanner(System.in);
		PrintWriter pw = new PrintWriter(System.out);
		int t = sc.nextInt();
		while (t-- > 0) {
			int n = sc.nextInt();
			adjList = new ArrayList[n];
			for (int i = 0; i < n; i++) {
				adjList[i] = new ArrayList<Integer>();
			}
			for (int i = 0; i < n - 1; i++) {
				int u = sc.nextInt();
				int v = sc.nextInt();
				adjList[u].add(v);
				adjList[v].add(u);
			}
			in = new int[n];
			out = new int[n];
			subTree = new long[n];
			dfs(0, -1);
			int[] end = { 1, -1 };
			int[] branch = new int[2];
			long[] ans = new long[n + 1];
			ans[0] = 1l * (n) * (n - 1) / 2;
			for (int x : adjList[0]) {
				ans[1] += subTree[x] * (n - subTree[x]);
				if (isChild(x, 1)) {
					ans[2] = subTree[1] * (n - subTree[x]);
					branch[0] = x;
				}
			}
			ans[1] += n - 1;
			ans[1] /= 2;

			for (int i = 2; i < n; i++) {
				if (isChild(i, end[0]) || (end[1] != -1 && isChild(i, end[1]))) {
					ans[i + 1] = ans[i];
					continue;
				}
				if (end[1] == -1) {
					if (isChild(end[0], i)) {
						end[0] = i;
						ans[i + 1] = subTree[end[0]] * (n - subTree[branch[0]]);
					} else {
						for (int x : adjList[0]) {
							if (isChild(x, i)) {
								branch[1] = x;
								break;
							}
						}
						if (branch[1] == branch[0])
							break;
						end[1] = i;
						ans[i + 1] = subTree[end[0]] * subTree[end[1]];
					}
				} else {
					boolean changed = false;
					for (int j = 0; j < 2; j++) {
						if (isChild(end[j], i)) {
							end[j] = i;
							changed = true;
						}
					}
					if (!changed)
						break;
					ans[i + 1] = subTree[end[0]] * subTree[end[1]];
				}
			}
//			pw.println(Arrays.toString(ans));
			for (int i = 0; i < n; i++) {
				ans[i] -= ans[i + 1];
			}
			for (long x : ans) {
				pw.print(x + " ");
			}
			pw.println();
		}
		pw.close();

	}

	static class Scanner {
		BufferedReader br;
		StringTokenizer st;

		public Scanner(InputStream s) {
			br = new BufferedReader(new InputStreamReader(s));
		}

		public Scanner(FileReader f) {
			br = new BufferedReader(f);
		}

		public String next() throws IOException {
			while (st == null || !st.hasMoreTokens())
				st = new StringTokenizer(br.readLine());
			return st.nextToken();
		}

		public int nextInt() throws IOException {
			return Integer.parseInt(next());
		}

		public long nextLong() throws IOException {
			return Long.parseLong(next());
		}

		public double nextDouble() throws IOException {
			return Double.parseDouble(next());
		}

		public int[] nextIntArr(int n) throws IOException {
			int[] arr = new int[n];
			for (int i = 0; i < n; i++) {
				arr[i] = Integer.parseInt(next());
			}
			return arr;
		}

	}

}