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 _721 {
    static ArrayList<Integer> [] adj;
    static int timer;
    static int [] inTime, outTime;
    static int [] sz;
    static int parent;
    static int [] lookup;
    public static void main(String[] args) {
        MyScanner sc = new MyScanner();
        PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
        int t = sc.nextInt();
        while (t-- > 0) {
            int n = sc.nextInt();
            adj = new ArrayList[n];
            for (int i = 0; i < n; i++) adj[i] = new ArrayList<>();
            inTime = new int[n];
            outTime = new int[n];
            timer = 0;
            for (int i = 0; i < n - 1; i++) {
                int a = sc.nextInt();
                int b = sc.nextInt();
                adj[a].add(b);
                adj[b].add(a);
            }
            int maxSize = 0;
            for (int i = 0; i < n; i++) maxSize = Math.max(maxSize, adj[i].size());
            sz = new int[n];
            dfs(0, -1);
            // how many paths have mex at least i
            long [] res = new long[n + 1];
            long total = ((long) n * (n - 1)) / 2;
            res[1] = total;
            for (Integer child: adj[0]) {
                res[0] += ((long) sz[child] * (sz[child] - 1)) / 2;
                res[1] -= ((long) sz[child] * (sz[child] - 1)) / 2;
            }
            lookup = new int[n];
            for (Integer i: adj[0]) {
                parent = i;
                dfs2(i, 0);
            }

            // LCA stuff

            log = (int)Math.ceil(Math.log(n) / Math.log(2));
            memo = new int[n + 1][log + 1];

            depth = new int[n + 1];

            for (int i = 0; i <= n; i++)
                Arrays.fill(memo[i], -1);
            dfs0(0, 0);

            int l = 0; int r = 0;
            for (int i = 2; i <= n; i++) {
                int connect = i - 1;
                if (isAncestor(connect, l) || isAncestor(connect, r)) {
                    res[i] = res[i - 1];
                } else if (isAncestor(l, connect) && lca(r, connect) == 0) {
                    l = connect;
                    if (r == 0) {
                        res[i] = ((long) sz[l] * (n - sz[lookup[l]]));
                    } else {
                        res[i] = ((long) sz[l] * sz[r]);
                    }
                } else if (isAncestor(r, connect) && lca(l, connect) == 0) {
                    r = connect;
                    if (l == 0) {
                        res[i] = ((long) sz[r] * (n - sz[lookup[r]]));
                    } else {
                        res[i] = ((long) sz[l] * sz[r]);
                    }
                } else {
                    for (int j = i; j <= n; j++) res[j] = 0;
                    break;
                }
            }
            out.print(res[0] + " ");
            for (int i = 1; i < n; i++) out.print((res[i] - res[i + 1]) + " ");
            if (maxSize <= 2) out.print(1);
            else out.print(0);
            out.println();
        }
        out.close();
    }

    static void dfs(int cur, int par) {
        inTime[cur] = timer++;
        sz[cur] = 1;
        for (Integer next: adj[cur]) {
            if (next != par) {
                dfs(next, cur);
                sz[cur] += sz[next];
            }
        }
        outTime[cur] = timer++;
    }

    static void dfs2(int cur, int par) {
        lookup[cur] = parent;
        for (Integer next: adj[cur]) {
            if (next != par) {
                dfs2(next, cur);
            }
        }
    }

    // is u an ancestor of v
    static boolean isAncestor(int u, int v) {
        return inTime[u] <= inTime[v] &&
                outTime[v] <= outTime[u];
    }

    static int[][] memo;
    static int [] depth;
    static int log;

    static void dfs0(int u, int p)
    {

        // Using recursion formula to calculate
        // the values of memo[][]
        memo[u][0] = p;
        for (int i = 1; i <= log; i++)
            memo[u][i] = memo[memo[u][i - 1]][i - 1];
        for (int v : adj[u]) {
            if (v != p) {

                // Calculating the level of each node
                depth[v] = depth[u] + 1;
                dfs0(v, u);
            }
        }
    }

    static int lca(int u, int v)
    {
        // The node which is present farthest
        // from the root node is taken as u
        // If v is farther from root node
        // then swap the two
        if (depth[u] < depth[v]) {
            int temp = u;
            u = v;
            v = temp;
        }

        // Finding the ancestor of u
        // which is at same level as v
        for (int i = log; i >= 0; i--) {
            if ((depth[u] - (int)Math.pow(2, i)) >= depth[v])
                u = memo[u][i];
        }

        // If v is the ancestor of u
        // then v is the LCA of u and v
        if (u == v)
            return u;

        // Finding the node closest to the root which is
        // not the common ancestor of u and v i.e. a node
        // x such that x is not the common ancestor of u
        // and v but memo[x][0] is
        for (int i = log; i >= 0; i--) {
            if (memo[u][i] != memo[v][i]) {
                u = memo[u][i];
                v = memo[v][i];
            }
        }

        // Returning the first ancestor
        // of above found node
        return memo[u][0];
    }


    static void sort(int[] a) {
        ArrayList<Integer> q = new ArrayList<>();
        for (int i : a) q.add(i);
        Collections.sort(q);
        for (int i = 0; i < a.length; i++) a[i] = q.get(i);
    }

    static void sort(long[] a) {
        ArrayList<Long> q = new ArrayList<>();
        for (long i : a) q.add(i);
        Collections.sort(q);
        for (int i = 0; i < a.length; i++) a[i] = q.get(i);
    }


    //-----------MyScanner class for faster input----------
    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;
        }


    }

}