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.math.BigInteger;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.StringTokenizer;

public class D {

  public static int time = 0;
  public static int[] starttime;
  public static int[] endtime;
  public static int[] forefather;
  public static int[] height;
  public static int[] countOfSubtree;

  public static void main(String[] args) {
    // Write code here
    FastScanner fs = new FastScanner();
    int t = fs.nextInt();
    while (t-- > 0) {
      int n = fs.nextInt();
      HashMap<Integer, ArrayList<Integer>> graph = new HashMap<>();
      for (int i = 0; i < n; i++) {
        graph.put(i, new ArrayList<>());
      }
      for (int i = 0; i < n - 1; i++) {
        int u = fs.nextInt();
        int v = fs.nextInt();
        graph.get(u).add(v);
        graph.get(v).add(u);
      }

      // Pre-Calculate
      time = 0;
      starttime = new int[n];
      endtime = new int[n];
      forefather = new int[n];
      height = new int[n];
      countOfSubtree = new int[n];
      Initialize(graph, 0, -1, 0, -1);

      // Main calculate
      long last = 0;
      for (int v : graph.get(0)) {
        int m = countOfSubtree[v];
        last += ((long)m * ((long)m - 1)) / 2;
      }
      System.out.print(last + " ");

      long remaining = (((long)n * ((long)n - 1)) / 2) - last;
      int a = 0, b = 0;
      long new_rem = 0;
      for (int i = 1; i < n; i++) {
        if (remaining == 0) {
          System.out.print("0 ");
          continue;
        }
        if (isAncestor(i, a) || isAncestor(i, b)){
          System.out.print("0 ");
          continue;
        }
        if (isAncestor(a, i)) {
          a = i;
        }
        else if (isAncestor(b, i)) {
          if (forefather[i] == forefather[a]) {
            System.out.print(remaining + " ");
            remaining = 0;
            continue;
          }
          b = i;
        } else {
          System.out.print(remaining + " ");
          remaining = 0;
          continue;
        }
        new_rem = calc(a, b);
        last = remaining - new_rem;
        System.out.print(last + " ");
        remaining = new_rem;
      }
      System.out.println(remaining);
    }
  }

  public static long calc(int a, int b) {
    if (b==0) return calc(b, a);
    if (a==0) {
      return ((long)countOfSubtree[0] - (long)countOfSubtree[forefather[b]]) * (long)countOfSubtree[b];
    }
    return (long)countOfSubtree[a] * (long)countOfSubtree[b];
  }

  // x is ancestor of y
  public static boolean isAncestor(int x, int y) {
    if (starttime[x] < starttime[y] && endtime[x] >= endtime[y]) {
      return true;
    }
    return false;
  }

  private static int Initialize(HashMap<Integer, ArrayList<Integer>> graph, int u, int parent,
      int h, int ff) {
    if (h == 1) {
      ff = u;
    }
    int count = 1;
    starttime[u] = time++;
    for (int v : graph.getOrDefault(u, new ArrayList<Integer>())) {
      if (v == parent) {
        continue;
      }
      count += Initialize(graph, v, u, h + 1, ff);
    }
    countOfSubtree[u] = count;
    height[u] = h;
    endtime[u] = time;
    forefather[u] = ff;

    return count;
  }

  private static int gcdThing(int a, int b) {
    BigInteger b1 = BigInteger.valueOf(a);
    BigInteger b2 = BigInteger.valueOf(b);
    BigInteger gcd = b1.gcd(b2);
    return gcd.intValue();
  }

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

  static class FastScanner {

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer("");

    String next() {
      while (!st.hasMoreTokens()) {
        try {
          st = new StringTokenizer(br.readLine());
        } catch (IOException e) {
          e.printStackTrace();
        }
      }
      return st.nextToken();
    }

    int nextInt() {
      return Integer.parseInt(next());
    }

    int[] readArray(int n) {
      int[] a = new int[n];
      for (int i = 0; i < n; i++) {
        a[i] = nextInt();
      }
      return a;
    }

    long nextLong() {
      return Long.parseLong(next());
    }
  }
}