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

public class CF_1527_D{
    //SOLUTION BEGIN
    int B = 22;
    void pre() throws Exception{}
    void solve(int TC) throws Exception{
        int N = ni();
        int[] from = new int[N - 1], to = new int[N - 1];
        for (int i = 0; i < N - 1; i++) {
            from[i] = ni();
            to[i] = ni();
        }
        int[][] tree = make(N, N - 1, from, to, true);
        long[] ans = new long[1 + N];
        long[] sub = new long[N];
        int[] d = new int[N];
        int[][] par = new int[B][N];
        for (int b = 0; b < B; b++) Arrays.fill(par[b], -1);

        dfs(tree, par, sub, d, 0, -1);
        ans[0] = (sub[0] * (sub[0] - 1)) / 2;
        ans[1] = ans[0];
        for (int v : tree[0])
            ans[1] -= (sub[v] * (sub[v] - 1)) / 2;
        boolean path = true;
        int p1 = 0, p2 = 1;
        boolean[] inc = new boolean[N];
        for(int u = 1; u != -1; u = par[0][u])inc[u] = true;
        for (int value = 2; value < N; value++) {
            int u = value;
            if (inc[u]) {
                ans[value] = ways(par, d, sub, p1, p2);
                continue;
            }
            while (!inc[u]) {
                inc[u] = true;
                u = par[0][u];
            }
            if (u != p1 && u != p2) {
                ans[value] = ways(par, d, sub, p1, p2);
                path = false;
                break;
            }
            ans[value] = ways(par, d, sub, p1, p2);
            if (u == p1) p1 = value;
            else p2 = value;
        }
        if (path) ans[N] = 1;
        for (int i = 1; i <= N; i++) ans[i - 1] -= ans[i];
        for (long i : ans) p(i);
        pn("");
    }
    long ways(int[][] par, int[] d, long[] sub, int u, int v) throws Exception{
        hold(u != v);
        long s1 = sub[u], s2 = sub[v];
        if(d[u] > d[v]){
            int tmp = u;
            u = v;
            v = tmp;
        }
        int lca = lca(par, d, u, v);
        if(lca == u)
            s1 -= sub[lift(par, v, d[v]-d[u]-1)];
        return s1*s2;
    }

    void dfs(int[][] tree, int[][] par, long[] sub, int[] d, int u, int p){
        sub[u]++;
        par[0][u] = p;
        for(int b = 1; b< B; b++)
            if(par[b-1][u] != -1)
                par[b][u] = par[b-1][par[b-1][u]];
        for(int v:tree[u]){
            if(v == p)continue;
            d[v] = d[u]+1;
            dfs(tree, par, sub, d, v, u);
            sub[u] += sub[v];
        }
    }
    int lca(int[][] par, int[] d, int u, int v){
        if(d[u] > d[v])u = lift(par, u, d[u]-d[v]);
        if(d[v] > d[u])v = lift(par, v, d[v]-d[u]);
        if(u == v)return u;
        for(int b = B-1; b > 0; b--)
            if(par[b][u] != par[b][v]){
                u = par[b][u];
                v = par[b][v];
            }
        return par[0][u];
    }
    int lift(int[][] par, int u, int x){
        for(int b = B-1; b >= 0; b--)
            if(((x>>b)&1)==1)
                u = par[b][u];
            return u;
    }
    //SOLUTION END
    void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
    void exit(boolean b){if(!b)System.exit(0);}
    static void dbg(Object... o){System.err.println(Arrays.deepToString(o));}
    final long IINF = (long)1e17;
    final int INF = (int)1e9+2;
    DecimalFormat df = new DecimalFormat("0.00000000000");
    double PI = 3.141592653589793238462643383279502884197169399, eps = 1e-8;
    static boolean multipleTC = true, memory = true, fileIO = false;
    FastReader in;PrintWriter out;
    void run() throws Exception{
        long ct = System.currentTimeMillis();
        if (fileIO) {
            in = new FastReader("");
            out = new PrintWriter("");
        } else {
            in = new FastReader();
            out = new PrintWriter(System.out);
        }
        //Solution Credits: Taranpreet Singh
        int T = multipleTC? ni():1;
        pre();
        for (int t = 1; t <= T; t++) solve(t);
        out.flush();
        out.close();
        System.err.println(System.currentTimeMillis() - ct);
    }
    public static void main(String[] args) throws Exception{
        if(memory)new Thread(null, new Runnable() {public void run(){try{new CF_1527_D().run();}catch(Exception e){e.printStackTrace();System.exit(1);}}}, "1", 1 << 28).start();
        else new CF_1527_D().run();
    }
    int[][] make(int n, int e, int[] from, int[] to, boolean f){
        int[][] g = new int[n][];int[]cnt = new int[n];
        for(int i = 0; i< e; i++){
            cnt[from[i]]++;
            if(f)cnt[to[i]]++;
        }
        for(int i = 0; i< n; i++)g[i] = new int[cnt[i]];
        for(int i = 0; i< e; i++){
            g[from[i]][--cnt[from[i]]] = to[i];
            if(f)g[to[i]][--cnt[to[i]]] = from[i];
        }
        return g;
    }
    int[][][] makeS(int n, int e, int[] from, int[] to, boolean f){
        int[][][] g = new int[n][][];int[]cnt = new int[n];
        for(int i = 0; i< e; i++){
            cnt[from[i]]++;
            if(f)cnt[to[i]]++;
        }
        for(int i = 0; i< n; i++)g[i] = new int[cnt[i]][];
        for(int i = 0; i< e; i++){
            g[from[i]][--cnt[from[i]]] = new int[]{to[i], i, 0};
            if(f)g[to[i]][--cnt[to[i]]] = new int[]{from[i], i, 1};
        }
        return g;
    }
    int find(int[] set, int u){return set[u] = (set[u] == u?u:find(set, set[u]));}
    int digit(long s){int ans = 0;while(s>0){s/=10;ans++;}return ans;}
    long gcd(long a, long b){return (b==0)?a:gcd(b,a%b);}
    int gcd(int a, int b){return (b==0)?a:gcd(b,a%b);}
    int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
    void p(Object... o){for(Object oo:o)out.print(oo+" ");}
    void pn(Object... o){for(int i = 0; i< o.length; i++)out.print(o[i]+(i+1 < o.length?" ":"\n"));}
    void pni(Object... o){for(Object oo:o)out.print(oo+" ");out.println();out.flush();}
    String n()throws Exception{return in.next();}
    String nln()throws Exception{return in.nextLine();}
    int ni()throws Exception{return Integer.parseInt(in.next());}
    long nl()throws Exception{return Long.parseLong(in.next());}
    double nd()throws Exception{return Double.parseDouble(in.next());}

    class FastReader{
        BufferedReader br;
        StringTokenizer st;
        public FastReader(){
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        public FastReader(String s) throws Exception{
            br = new BufferedReader(new FileReader(s));
        }

        String next() throws Exception{
            while (st == null || !st.hasMoreElements()){
                try{
                    st = new StringTokenizer(br.readLine());
                }catch (IOException  e){
                    throw new Exception(e.toString());
                }
            }
            return st.nextToken();
        }

        String nextLine() throws Exception{
            String str;
            try{
                str = br.readLine();
            }catch (IOException e){
                throw new Exception(e.toString());
            }
            return str;
        }
    }
}