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.math.*;
import java.text.*;
import java.util.*;

public class Main {
	static PrintWriter out;
	static Reader in;
	public static void main(String[] args) throws IOException {
		input_output();
		Main solver = new Main();
		solver.solve();
		out.close();

		out.flush();
	}

	static long INF = (long)1e18;
	static int MAXN = (int)4e5 + 5;
	static int MOD = (int)1e9 + 7;
	static int q, t, n, m, k;
	static double pi = Math.PI;

	static List<Integer> adj[];

	void solve() throws IOException {
		t = in.nextInt();

		while (t -- > 0) {
			n = in.nextInt();

			adj = new ArrayList[n];
			for (int i = 0; i < n; i++) adj[i] = new ArrayList<>();

			for (int i = 0; i < n - 1; i++) {
				int u = in.nextInt(),
				    v = in.nextInt();
				adj[u].add(v);
				adj[v].add(u);
			}

			visOne = new boolean[n];
			visOne[1] = true;
			size = new long[n+1];
			enter = new int[n+1];
			leave = new int[n+1];
			par = new int[n];
			dfs(0, -1);

			long[] ans = new long[n + 1];

			// calculate 0s
			for (int e : adj[0]) {
				ans[0] += (size[e]*(size[e]-1))/2;
			}

			// calculate 1s
			long all = 0, down = 0;
			for (int e : adj[0]) {
				if (e != special) all += size[e];
				else all += size[e] - size[1];
			}
			for (int e : adj[0]) {
				long tmp = size[e];
				if (e == special) tmp = size[e] - size[1];
				ans[1] += tmp*(all-tmp);
				down += tmp;
			}
			ans[1] = ans[1] / 2 + down;

			// calculate xs >= 2s
			int first = 0, second = 1, leaf = 0;
			TreeSet<Integer> set = new TreeSet<>(); // to keep track of elements in the path
			for (int i = 1; i <= n; i++) set.add(i);
			loop:while (set.size() != 0) {
				int next = set.first();
				set.remove(next);
				leaf = next;

				if (leaf == n) {
					ans[leaf] = 1;
					break;
				}

				while (true) {
					if (set.contains(par[next])) {
						set.remove(par[next]);
						next = par[next];
					} else {
						if (first == par[next] || second == par[next]) {
							if (leaf != 1) {
								if (first == par[next]) {
									first = leaf; 
								} else {
									second = leaf;
								}
							}
							break;
						} else {
							break loop;
						}
					}
				}


				int value = set.first();
				long left = find(first, value),
					 right = find(second, value);
				ans[value] += left*right;
			}

			for (int i = 0; i <= n; i++) out.print(ans[i] + (i == n ? "\n" : " "));
		}
	}

	static long find(int s, int next) {
		long ret = 0;
		if (s != 0) ret =  size[s];
		else ret = size[s] - size[special];

		if (s != 0) {
			if (enter[s] <= enter[next] && enter[next] <= leave[s]) {
				ret -= size[next];
			}
		} else {
			if (enter[next] < enter[special] || leave[special] < enter[next]) {
				ret -= size[next];
			}
		}

		return ret;
	}

	static int special = 0;
	static boolean[] visOne;
	static long[] size;
	static int enter[], leave[], par[], cnt = 0;

	static void dfs(int s, int p) {
		size[s] = 1;
		par[s] = p;
		enter[s] = leave[s] = cnt++;

		for (int e : adj[s]) {
			if (e == p) continue;

			dfs(e, s);
			visOne[s] |= visOne[e];
			size[s] += size[e];
			leave[s] = leave[e];

			if (s == 0 && visOne[e]) {
				special = e;
			}
		}
	}

	static class Reader {
		private InputStream mIs;
		private byte[] buf = new byte[1024];
		private int curChar;
		private int numChars;

		public Reader() {
			this(System.in);
		}

		public Reader(InputStream is) {
			mIs = is;
		}

		public int read() {
			if (numChars == -1) {
				throw new InputMismatchException();

			}
			if (curChar >= numChars) {
				curChar = 0;
				try {
					numChars = mIs.read(buf);
				} catch (IOException e) {
					throw new InputMismatchException();
				}
				if (numChars <= 0) {
					return -1;
				}
			}
			return buf[curChar++];
		}

		public String nextLine() {
			int c = read();
			while (isSpaceChar(c)) {
				c = read();
			}
			StringBuilder res = new StringBuilder();
			do {
				res.appendCodePoint(c);
				c = read();
			} while (!isEndOfLine(c));
			return res.toString();
		}

		public String next() {
			int c = read();
			while (isSpaceChar(c)) {
				c = read();
			}
			StringBuilder res = new StringBuilder();
			do {
				res.appendCodePoint(c);
				c = read();
			} while (!isSpaceChar(c));
			return res.toString();
		}

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

		public long nextLong() {
			int c = read();
			while (isSpaceChar(c)) {
				c = read();
			}
			int sgn = 1;
			if (c == '-') {
				sgn = -1;
				c = read();
			}
			long res = 0;
			do {
				if (c < '0' || c > '9') {
					throw new InputMismatchException();
				}
				res *= 10;
				res += c - '0';
				c = read();
			} while (!isSpaceChar(c));
			return res * sgn;
		}

		public int nextInt() {
			int c = read();
			while (isSpaceChar(c)) {
				c = read();
			}
			int sgn = 1;
			if (c == '-') {
				sgn = -1;
				c = read();
			}
			int res = 0;
			do {
				if (c < '0' || c > '9') {
					throw new InputMismatchException();
				}
				res *= 10;
				res += c - '0';
				c = read();
			} while (!isSpaceChar(c));
			return res * sgn;
		}

		public boolean isSpaceChar(int c) {
			return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
		}

		public boolean isEndOfLine(int c) {
			return c == '\n' || c == '\r' || c == -1;
		}

	}
	static void input_output() throws IOException {
		File f = new File("in.txt");
		if (f.exists() && !f.isDirectory()) {
			in = new Reader(new FileInputStream("in.txt"));
		} else in = new Reader();
		f = new File("out.txt");
		if (f.exists() && !f.isDirectory()) {
			out = new PrintWriter(new File("out.txt"));
		} else out = new PrintWriter(System.out);
	}
}