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.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.*;
import java.util.stream.Collectors;

public class SolutionD extends Thread {
    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            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;
        }
    }

    private static final FastReader scanner = new FastReader();
    private static final PrintWriter out = new PrintWriter(System.out);

    public static void main(String[] args) {
        new Thread(null, new SolutionD(), "Main", 1 << 28).start();
    }

    public void run() {
        int t = scanner.nextInt();
        for (int i = 0; i < t; i++) {
            solve();
        }
        out.close();
    }

    static class Node {
        //standard attributes
        int index;
        List<Node> neighbors;
        int minDesc;
        int amountDesc;

        //attributes for dfs
        boolean visited1;
        boolean visited2;


        public Node(int index) {
            this.index = index;
            this.visited1 = false;
            this.visited2 = false;
            this.neighbors = new ArrayList<>();
        }

        int dfs1() {
            visited1 = true;
            amountDesc = 1;
            minDesc = Integer.MAX_VALUE;
            for (Node neighbor: neighbors) {
                if (!neighbor.visited1) {
                    minDesc = Math.min(minDesc, neighbor.dfs1());
                    amountDesc += neighbor.amountDesc;
                }
            }
            return Math.min(index, minDesc);
        }

        int dfs2(int find) {
            visited2 = true;
            if (this.index == find) {
                return 0;
            }
            int result = 1;
            for (Node neighbor : neighbors) {
                if (neighbor.visited2) {
                    continue;
                }
                if (neighbor.index == find || neighbor.minDesc == find) {
                    result += neighbor.dfs2(find);
                } else {
                    result += neighbor.amountDesc;
                }
            }
            return result;
        }
    }

    private static void solve() {
        int n = scanner.nextInt();
        Node[] nodes = new Node[n];
        for (int i = 0; i < n; i++) {
            nodes[i] = new Node(i);
        }
        for (int i = 0; i < n-1; i++) {
            int ui = scanner.nextInt();
            int vi = scanner.nextInt();
            nodes[ui].neighbors.add(nodes[vi]);
            nodes[vi].neighbors.add(nodes[ui]);
        }

        nodes[0].dfs1();
        long[] output = new long[n+1];
        int amountDesc = 0;

        int minChildIndex = -1;
        int amountDescMinChild = 0;

        nodes[0].visited2 = true;
        for (int i = 0; i < nodes[0].neighbors.size(); i++) {
            Node child = nodes[0].neighbors.get(i);

            if (child.index == 1 || child.minDesc == 1) {
                amountDescMinChild = child.dfs2(1);
                amountDesc += amountDescMinChild;
                minChildIndex = child.index;
            } else {
                amountDesc += child.amountDesc;
            }

            output[0] += child.amountDesc * (long) (child.amountDesc-1) / 2L;
        }

        output[1] = amountDesc * 2L;
        for (Node child: nodes[0].neighbors) {
            if (child.index == minChildIndex) {
                output[1] += (long) amountDescMinChild * (amountDesc - amountDescMinChild);
            } else {
                output[1] += (long) child.amountDesc * (amountDesc - child.amountDesc);
            }
        }
        output[1] /= 2L;

        Node a = nodes[0];
        Node b = nodes[1];

        a.minDesc = Integer.MAX_VALUE;
        for (int j = 0; j < a.neighbors.size(); j++) {
            if (!a.neighbors.get(j).visited2) {
                a.minDesc = Math.min(a.minDesc, Math.min(a.neighbors.get(j).index, a.neighbors.get(j).minDesc));
            }
        }


        for (int i = 2; i <= n; i++) {
            if (i < n && nodes[i].visited2) {
                continue;
            }

            if (a.minDesc != i && b.minDesc != i) {
                if (a.index != 0) {
                    output[i] = (long) (a.amountDesc) * (b.amountDesc);
                } else {
                    output[i] = (long) (a.amountDesc - nodes[minChildIndex].amountDesc) * (b.amountDesc);
                }
                break;
            } else if (a.minDesc == i) {
                output[i] = (long) b.amountDesc * a.dfs2(i);
                a = nodes[i];
            } else if (a.index != 0) {
                output[i] = (long) a.amountDesc * b.dfs2(i);
                b = nodes[i];
            } else {
                output[i] = (long) (a.amountDesc - nodes[minChildIndex].amountDesc) * b.dfs2(i);
                b = nodes[i];
            }
        }

        out.println(Arrays.stream(output).mapToObj(String::valueOf).collect(Collectors.joining(" ")));
    }
}