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:
/*
bts songs to dance to:
I need U
Run
ON
Filter
I'm fine
 */
import static java.lang.Math.max;
import static java.lang.Math.min;
import static java.lang.Math.abs;
import static java.lang.System.out;
import java.util.*;
import java.io.*;
import java.math.*;

public class x1527D
{
    static int[][] edges;
    public static void main(String hi[]) throws Exception
    {
        FastScanner infile = new FastScanner();
        int T = infile.nextInt();
        StringBuilder sb = new StringBuilder();
        while(T-->0)
        {
            int N = infile.nextInt();
            edges = new int[N][];
            int[] freq = new int[N];
            ArrayDeque<Integer> input = new ArrayDeque<Integer>();
            for(int i=1; i < N; i++)
            {
                int a = infile.nextInt();
                int b = infile.nextInt();
                freq[a]++;  freq[b]++;
                input.add(a);   input.add(b);
            }
            for(int i=0; i < N; i++)
                edges[i] = new int[freq[i]];
            while(input.size() > 0)
            {
                int a = input.poll();
                int b = input.poll();
                edges[a][--freq[a]] = b;
                edges[b][--freq[b]] = a;
            }
            size = new int[N];
            parent = new int[N];
            dfs(0, -1);
            boolean[] seen = new boolean[N];
            int left = 0, right = 0;
            seen[0] = true;
            long[] res = new long[N+2];
            res[0] = (long)N*(N-1)/2;
            long boof = 1L;
            for(int child: edges[0])
            {
                res[1] += boof*size[child];
                boof += size[child];
            }
            for(int mex=1; mex < N; mex++)
            {
                int curr = mex;
                if(seen[curr])
                {
                    res[mex+1] = (long)size[left]*size[right];
                    continue;
                }
                seen[curr] = true;
                while(!seen[parent[curr]])
                {
                    seen[parent[curr]] = true;
                    curr = parent[curr];
                }
                if(parent[curr] == left)
                {
                    size[parent[curr]] -= size[curr];
                    left = mex;
                }
                else if(parent[curr] == right)
                {
                    size[parent[curr]] -= size[curr];
                    right = mex;
                }
                else
                {
                    //System.out.println("KEKW "+left+" "+right+" "+curr+" "+parent[curr]);
                    break;
                }
                res[mex+1] = (long)size[left]*size[right];
            }
            for(int i=0; i <= N; i++)
                sb.append(res[i]-res[i+1]).append(" ");
            sb.append("\n");
        }
        System.out.print(sb);
    }
    static int[] size;
    static int[] parent;
    public static void dfs(int curr, int par)
    {
        parent[curr] = par;
        size[curr] = 1;
        for(int next: edges[curr])
            if(next != par)
            {
                dfs(next, curr);
                size[curr] += size[next];
            }
    }
}
class FastScanner
{
    private int BS = 1 << 16;
    private char NC = (char) 0;
    private byte[] buf = new byte[BS];
    private int bId = 0, size = 0;
    private char c = NC;
    private double cnt = 1;
    private BufferedInputStream in;

    public FastScanner() {
        in = new BufferedInputStream(System.in, BS);
    }

    public FastScanner(String s) {
        try {
            in = new BufferedInputStream(new FileInputStream(new File(s)), BS);
        } catch (Exception e) {
            in = new BufferedInputStream(System.in, BS);
        }
    }

    private char getChar() {
        while (bId == size) {
            try {
                size = in.read(buf);
            } catch (Exception e) {
                return NC;
            }
            if (size == -1) return NC;
            bId = 0;
        }
        return (char) buf[bId++];
    }

    public int nextInt() {
        return (int) nextLong();
    }

    public int[] nextInts(int N) {
        int[] res = new int[N];
        for (int i = 0; i < N; i++) {
            res[i] = (int) nextLong();
        }
        return res;
    }

    public long[] nextLongs(int N) {
        long[] res = new long[N];
        for (int i = 0; i < N; i++) {
            res[i] = nextLong();
        }
        return res;
    }

    public long nextLong() {
        cnt = 1;
        boolean neg = false;
        if (c == NC) c = getChar();
        for (; (c < '0' || c > '9'); c = getChar()) {
            if (c == '-') neg = true;
        }
        long res = 0;
        for (; c >= '0' && c <= '9'; c = getChar()) {
            res = (res << 3) + (res << 1) + c - '0';
            cnt *= 10;
        }
        return neg ? -res : res;
    }

    public double nextDouble() {
        double cur = nextLong();
        return c != '.' ? cur : cur + nextLong() / cnt;
    }

    public double[] nextDoubles(int N) {
        double[] res = new double[N];
        for (int i = 0; i < N; i++) {
            res[i] = nextDouble();
        }
        return res;
    }

    public String next() {
        StringBuilder res = new StringBuilder();
        while (c <= 32) c = getChar();
        while (c > 32) {
            res.append(c);
            c = getChar();
        }
        return res.toString();
    }

    public String nextLine() {
        StringBuilder res = new StringBuilder();
        while (c <= 32) c = getChar();
        while (c != '\n') {
            res.append(c);
            c = getChar();
        }
        return res.toString();
    }

    public boolean hasNext() {
        if (c > 32) return true;
        while (true) {
            c = getChar();
            if (c == NC) return false;
            else if (c > 32) return true;
        }
    }
}