#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 200010;

ll ans[N];
bool path[N];
vector <int> g[N];
int t, n, sub[N], p[N], ptr, in[N], out[N];

void go (int u, int par = -1) {
  in[u] = ++ptr;
  sub[u] = 1, p[u] = par;
  for (int v : g[u]) if (v != par and !path[v]) {
    go(v, u);
    sub[u] += sub[v];
  } 
  out[u] = ptr;
}

int main() {
  cin >> t;
  while (t--) {
    cin >> n;
    for (int i = 0; i <= n; ++i) {
      g[i].clear(); path[i] = 0; 
      ans[i] = in[i] = out[i] = 0;
    }
    for (int i = 1, u, v; i < n; ++i) {
      scanf("%d %d", &u, &v);
      g[u].emplace_back(v);
      g[v].emplace_back(u);
    }
    ptr = 0; go(0);
    { // zero
      for (int u : g[0]) ans[0] += (ll) sub[u] * (sub[u] - 1) / 2;
    }
    { // one
      ans[1] += (ll) n * (n - 1) / 2 - ans[0];
      int u = 1;
      while (p[u]) u = p[u];
      ans[1] -= (ll) sub[1] * (n - sub[u]);
    }
    { // mark path
      int u = 1;
      while (u) path[u] = 1, u = p[u];
      path[0] = 1; ptr = 0; 
      for (int i = 0; i <= n; ++i) in[i] = out[i] = 0;
      go(0); go(1);
    }
    // for (int i = 0; i < n; ++i) cerr << sub[i] << " "; cerr << '\n';
    int A = 0, B = 1;
    for (int mex = 2; mex <= n; ++mex) {
      if (!path[mex]) {
        ll one = sub[A], two = sub[B];
        if (in[A] <= in[mex] and in[mex] <= out[A]) one -= sub[mex];
        if (in[B] <= in[mex] and in[mex] <= out[B]) two -= sub[mex];
        // cerr << mex << " --> " << one << " " << two << '\n';
        ans[mex] += one * two;
        if (in[A] <= in[mex] and in[mex] <= out[A]) {
          int u = mex;
          while (u ^ A) path[u] = 1, u = p[u];
          A = mex;
        }
        if (in[B] <= in[mex] and in[mex] <= out[B]) {
          int u = mex;
          while (u ^ B) path[u] = 1, u = p[u];
          B = mex;
        }
      }
      if (!path[mex]) break;
    }
    for (int i = 0; i <= n; ++i) printf("%lld ", ans[i]); puts("");
  }
  return 0;
}


### Prompt

Generate a Cpp solution to the following 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. 

### Response

```cpp
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 200010;

ll ans[N];
bool path[N];
vector <int> g[N];
int t, n, sub[N], p[N], ptr, in[N], out[N];

void go (int u, int par = -1) {
  in[u] = ++ptr;
  sub[u] = 1, p[u] = par;
  for (int v : g[u]) if (v != par and !path[v]) {
    go(v, u);
    sub[u] += sub[v];
  } 
  out[u] = ptr;
}

int main() {
  cin >> t;
  while (t--) {
    cin >> n;
    for (int i = 0; i <= n; ++i) {
      g[i].clear(); path[i] = 0; 
      ans[i] = in[i] = out[i] = 0;
    }
    for (int i = 1, u, v; i < n; ++i) {
      scanf("%d %d", &u, &v);
      g[u].emplace_back(v);
      g[v].emplace_back(u);
    }
    ptr = 0; go(0);
    { // zero
      for (int u : g[0]) ans[0] += (ll) sub[u] * (sub[u] - 1) / 2;
    }
    { // one
      ans[1] += (ll) n * (n - 1) / 2 - ans[0];
      int u = 1;
      while (p[u]) u = p[u];
      ans[1] -= (ll) sub[1] * (n - sub[u]);
    }
    { // mark path
      int u = 1;
      while (u) path[u] = 1, u = p[u];
      path[0] = 1; ptr = 0; 
      for (int i = 0; i <= n; ++i) in[i] = out[i] = 0;
      go(0); go(1);
    }
    // for (int i = 0; i < n; ++i) cerr << sub[i] << " "; cerr << '\n';
    int A = 0, B = 1;
    for (int mex = 2; mex <= n; ++mex) {
      if (!path[mex]) {
        ll one = sub[A], two = sub[B];
        if (in[A] <= in[mex] and in[mex] <= out[A]) one -= sub[mex];
        if (in[B] <= in[mex] and in[mex] <= out[B]) two -= sub[mex];
        // cerr << mex << " --> " << one << " " << two << '\n';
        ans[mex] += one * two;
        if (in[A] <= in[mex] and in[mex] <= out[A]) {
          int u = mex;
          while (u ^ A) path[u] = 1, u = p[u];
          A = mex;
        }
        if (in[B] <= in[mex] and in[mex] <= out[B]) {
          int u = mex;
          while (u ^ B) path[u] = 1, u = p[u];
          B = mex;
        }
      }
      if (!path[mex]) break;
    }
    for (int i = 0; i <= n; ++i) printf("%lld ", ans[i]); puts("");
  }
  return 0;
}


```