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.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;
import java.util.List;
 import java.util.*;
  public class realfast implements Runnable 
  {
    private static final int INF = (int) 1e9;
    long in= 1000000007;
    long fac[]= new long[1000001];
    long inv[]=new long[1000001];
    int timer=0;
    long dp[]=new long[2*100001];
    public  void solve() throws IOException 
    {

        //int t = readInt();
        
        int t = readInt();
             
       for(int f =0;f<t;f++)
       {
         int n = readInt();
        
         ArrayList<Integer> arr[]=new ArrayList[n];
         for(int i=0;i<n;i++)
            arr[i]= new ArrayList<Integer>();
         for(int i =0;i<n-1;i++)
         {
             int u = readInt();
             int v = readInt();
             arr[u].add(v);
             arr[v].add(u); 
         }
         for(int i=0;i<n;i++)
            dp[i]=0;
         timer=0;
         int depth[]=new int[n];
         int parent[]=new int[n];
         int in[]=new int[n];
          int out1[]=new int[n];
          int size[]=new int[n];
          //System.out.println("hello");
          dfs(arr,depth,parent,0,-1,in,out1,size);
           //System.out.println("hello");
          long ans[]=new long[n+1];
          long sum=1;
          for(int i =0;i<arr[0].size();i++)
          {
             int v = arr[0].get(i);
             long pal = size[v];
             ans[0]= ans[0]+ (pal*(pal-1))/2;
              ans[1]= ans[1]+ sum*pal;
              sum= sum+pal;
          }

          ans[2]=0;
          boolean mark[]=new boolean[n];
          mark[0]= true;
          int cur=1;
          while(cur!=0)
          {
                 mark[cur]= true;
                 cur=parent[cur];
          }
          long yo=1;
          long yo1=1;
          for(int i=0;i<arr[0].size();i++)
          {
            int v = arr[0].get(i);
            if(v!=parent[0]&&!mark[v])
            {
                yo= yo+size[v];
            }
          }
          for(int i=0;i<arr[1].size();i++)
          {
            int v = arr[1].get(i);
            if(v!=parent[1]&&!mark[v])
            {
                yo1= yo1+size[v];
            }
          }


          ans[2]= yo1*yo;
         // System.out.println(ans[2]);
         // System.out.println(ans[2]);
          ans[1]= ans[1]- ans[2];

          int end1=0;
          int end2=1;
          

          for(int i=2;i<=n-1;i++)
          {
               if(mark[i])
               {
                  ans[i+1]=ans[i];
                  ans[i]=0;
               }
               else 
               {
                   boolean yo2 = true;
                   if(depth[end1]>depth[end2])
                   {
                       if(in[i]>=in[end1]&&in[i]<=out1[end1])
                       {

                         if(!mark(mark,i,end1,parent))
                         {

                           break;
                         }
                         end1=i;
                         ans[i+1]= calculate(size,end1,end2,arr, mark,parent);
                         ans[i]= ans[i]-ans[i+1];
                         yo2=false;
                       }
                       else if(in[i]>=in[end2]&&in[i]<=out1[end2])
                       {
                         if(!mark(mark,i,end2,parent))
                         {
                               break;
                         }
                         end2=i;
                         ans[i+1]= calculate(size,end1,end2,arr, mark,parent);
                         ans[i]= ans[i]-ans[i+1];
                         yo2=false;
                       }
                   }
                   else
                   {

                       if(in[i]>=in[end2]&&in[i]<=out1[end2])
                       {
                         if(!mark(mark,i,end2,parent))
                         {
                            break;
                         }
                         end2=i;
                         ans[i+1]= calculate(size,end1,end2,arr, mark,parent);
                         ans[i]= ans[i]-ans[i+1];
                         yo2=false;
                       }
                       else if(in[i]>=in[end1]&&in[i]<=out1[end1])
                       {
                         if(!mark(mark,i,end1,parent))
                         {
                            break;
                         }
                         end1=i;
                         ans[i+1]= calculate(size,end1,end2,arr, mark,parent);
                         ans[i]= ans[i]-ans[i+1];
                         yo2=false;
                       }

                   }
                   
                   if(yo2)
                   {
                    break;
                   }
               }
          }

          for(int i=0;i<=n;i++)
            System.out.print(ans[i]+" ");


          System.out.println();


       }

        



    }
    public long calculate(int size[] , int i, int j , ArrayList<Integer> arr[] , boolean mark[], int parent[])
    {
        long yo=1;
        long yo1=1;
        if(dp[i]==0){
        for(int k =0;k<arr[i].size();k++)
        {
             int v = arr[i].get(k);
             if(v!=parent[i]&&(!mark[v]))
             {
                yo= yo+size[v];
             }
        }
        }
        else
        yo= dp[i];
        dp[i]=yo;
        if(dp[j]==0){
        for(int k =0;k<arr[j].size();k++)
        {
             int v = arr[j].get(k);
             if(v!=parent[j]&&(!mark[v]))
             {
                yo1= yo1+size[v];
             }
        }
       }
        else
            yo1=dp[j];

        dp[j]=yo1;

        return yo*yo1;


    }
    public boolean mark(boolean mark[] ,int start, int end , int parent[])
    {
              while(start!=end)
              {
                 if(mark[start])
                    return false;
                 mark[start]= true;
                 start= parent[start];
              }
             return true;
    }
    public void dfs(ArrayList<Integer> arr[] ,  int depth[] ,int parent[], int u , int par, int in[], int out[],int size[] )
    {

        parent[u]=par;
        if(par!=-1)
        depth[u]= depth[par]+1;
        timer++;
        in[u]= timer;
        size[u]=1;
        for(int j =0;j<arr[u].size();j++)
        {
         if(arr[u].get(j)!=par)
         {
            int v = arr[u].get(j);
            dfs(arr,depth, parent,v,u, in ,out,size);
            size[u]= size[u]+size[v];
          }
        }

        out[u]= timer;

    }

    
    
    public int value (int seg[], int left , int right ,int index, int l, int r)
    {
            
            if(left>right)
            {
              return -100000000;
            }
            if(right<l||left>r)
                return -100000000;
            if(left>=l&&right<=r)
                return seg[index];
            int mid = left+(right-left)/2;
            int val = value(seg,left,mid,2*index+1,l,r);
            int val2 = value(seg,mid+1,right,2*index+2,l,r);
            return Math.max(val,val2);

    }
   
    public int gcd(int a , int b )
    {
      if(a<b)
      {
        int t =a;
        a=b;
        b=t;
      }
      if(a%b==0)
        return b ;
      return gcd(b,a%b);
    }
    public long pow(long n , long p,long m)
    {
         if(p==0)
            return 1;
        long val = pow(n,p/2,m);;
        val= (val*val)%m;
        if(p%2==0)
            return val;
        else
            return (val*n)%m;
    }
    
    
    ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
    public static void main(String[] args) {
        new Thread(null, new realfast(), "", 128 * (1L << 20)).start();
    }
 
    private static final boolean ONLINE_JUDGE = System.getProperty("ONLINE_JUDGE") != null;
    private BufferedReader reader;
    private StringTokenizer tokenizer;
    private PrintWriter out;
 
    @Override
    public void run() {
        try {
            if (ONLINE_JUDGE || !new File("input.txt").exists()) {
                reader = new BufferedReader(new InputStreamReader(System.in));
                out = new PrintWriter(System.out);
            } else {
                reader = new BufferedReader(new FileReader("input.txt"));
                out = new PrintWriter("output.txt");
            }
            solve();
        } catch (IOException e) {
            throw new RuntimeException(e);
        } finally {
            try {
                reader.close();
            } catch (IOException e) {
                // nothing
            }
            out.close();
        }
    }
 
    private String readString() throws IOException {
        while (tokenizer == null || !tokenizer.hasMoreTokens()) {
            tokenizer = new StringTokenizer(reader.readLine());
        }
        return tokenizer.nextToken();
    }
 
    @SuppressWarnings("unused")
    private int readInt() throws IOException {
        return Integer.parseInt(readString());
    }
 
    @SuppressWarnings("unused")
    private long readLong() throws IOException {
        return Long.parseLong(readString());
    }
 
    @SuppressWarnings("unused")
    private double readDouble() throws IOException {
        return Double.parseDouble(readString());
    }
}
class edge implements Comparable<edge>{
    int u ;
    int v;
    
    edge(int u, int v)
    {
       this.u=u;
       this.v=v;
    }
    public int compareTo(edge e)
    {
        return this.v-e.v;
    }
}