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 CPP):

Solution:
#include <bits/stdc++.h>
#ifdef ALGO
#include "el_psy_congroo.hpp"
#else
#define DUMP(...) 1145141919810
#define CHECK(...) (__VA_ARGS__)
#endif

struct Dsu {
  std::vector<int> dsu;

  explicit Dsu(int size) : dsu(size) {
    std::iota(dsu.begin(), dsu.end(), 0);
  }

  int find(int x) {
    return dsu[x] == x ? x : dsu[x] = find(dsu[x]);
  }
};

using LL = long long;

LL binom2(int x) {
  if (x < 2) return 0;
  return x * 1LL * (x - 1) / 2;
}

struct Solver {
  int n;
  std::vector<std::vector<int>> edges;
  std::vector<int> sz;
  std::vector<int> parent;

  Solver(int n, std::vector<std::vector<int>> edges) : n(n), edges(edges), sz(n), parent(n, -1) {}

  void dfs(int u, int fa) {
    parent[u] = fa;
    sz[u] = 1;
    for (int v : edges[u]) if (v != fa) {
      dfs(v, u);
      sz[u] += sz[v];
    }
  }

  void solve() {
    dfs(0, -1);
    std::vector<LL> result(n + 1);
    for (int v : edges[0]) result[0] += binom2(sz[v]);
    std::set<int> eds;
    Dsu dsu(n);
    std::vector<bool> mark(n);
    mark[0] = true;
    std::set<int> r1;
    for (int u = 1; u < n; ++u) {
      if (!mark[u]) {
        eds.emplace(u);
        for (int v = u; ; v = dsu.find(v)) {
          mark[v] = true;
          int w = parent[v];
          if (w == 0) break;
          if (eds.count(w)) {
            eds.erase(w);
          }
          dsu.dsu[v] = w;
        }
      }
      r1.emplace(dsu.find(u));
      if (r1.size() != eds.size()) {
        break;
      }
      if (eds.size() == 2) {
        LL val = 1;
        for (int v : eds)
          val *= sz[v];
        result[u + 1] += val;
      } else if (eds.size() == 1) {
        LL val = sz[*eds.begin()];
        val *= n - sz[dsu.find(u)];
        result[u + 1] += val;
      }
      if (u > 1) result[u] -= result[u + 1];
    }
    result[1] = binom2(n) - std::accumulate(result.begin(), result.end(), 0LL);
    for (int i = 0; i <= n; ++i)
      printf("%lld%c", result[i], " \n"[i == n]);
  }
};

int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  std::istream& reader = std::cin;

  int cas;
  reader >> cas;
  while (cas--) {
    int n;
    reader >> n;
    std::vector<std::vector<int>> edges(n);
    for (int i = 0; i < n - 1; ++i) {
      int x, y;
      reader >> x >> y;
      edges[x].emplace_back(y);
      edges[y].emplace_back(x);
    }
    Solver(n, edges).solve();
  }
}