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>

using namespace std;

#define forn(I,N) for (int I = 0; I < N; ++I)
#define fornd(I,N) for (int I = N-1; I >= 0; --I)
#define forab(I,A,B) for (int I = A; I <= B; ++I)
#define forabd(I,A,B) for (int I = B; I >= A; --I)
#define foreach(I, A) for(typeof((A).begin()) I = (A).begin(); I != (A).end(); ++I)
// #define foreach(I, A) for((__typeof__(A))::iterator I = (A).begin(); I != (A).end(); ++I)

#define pb push_back
#define mp make_pair

typedef long long LL;

// sorting
struct P {
  int x, y;
  bool operator<(const P &p) {
    if (x != p.x) return x < p.x;
    else return y < p.y;
  }
};

/*
bool comp(data dt1, data dt2) {
  return dt1 < dt2;
}
*/

int main() {
  int T;
  cin >> T;

  forn (t, T) {
    int n;
    cin >> n;
    
    vector<vector<int> > neighbors(n);
    int a, b;
    forn (i, n - 1) {
      scanf("%d %d", &a, &b);
      neighbors[a].pb(b);
      neighbors[b].pb(a);
    }

    vector<int> leaf;
    vector<bool> taken(n);
    vector<int> ncount(n);
    forn (i, n) {
      ncount[i] = neighbors[i].size();
      if (i != 0 && neighbors[i].size() == 1) {
        leaf.pb(i);
        taken[i] = true;
      }
    }

    vector<LL> child(n);
    vector<int> parent(n, -1);
    forn (i, n - 1) {
      int ind = leaf[i];
      forn (j, neighbors[ind].size()) {
        int neighbor = neighbors[ind][j];
        if (!taken[neighbor]) {
          child[neighbor] += 1 + child[ind];
          parent[ind] = neighbor;
          ncount[neighbor]--;
          if (neighbor != 0 && ncount[neighbor] <= 1) {
            leaf.pb(neighbor);
            taken[neighbor] = true;
          }
        }
      }
    }

    vector<LL> mex(n + 1);
    vector<LL> tmex(n + 1);
    forn (i, neighbors[0].size()) {
      int ind = neighbors[0][i];
      mex[0] += (LL)child[ind] * (LL)(child[ind] + 1) / 2;
    }

    vector<bool> visited(n);
    visited[0] = true;
    int l = 0, r = 0;
    LL temp = 0;
    forn (i, neighbors[0].size()) {
      int neighbor = neighbors[0][i];
      tmex[0] += child[neighbor] + 1;
      temp += (child[neighbor]  + 1) * ((LL)n - child[neighbor] - 2);
    }
    tmex[0] += temp / 2;

    int non0 = -1;
    forab (i, 1, n - 1) {
      int ind = i;
      vector<int> toAdd;
      while(!visited[ind]) {
        toAdd.pb(ind);
        ind = parent[ind];
      }
      if (ind != i && ind != l && ind != r) {
        break;
      }

      if (ind == r) {
        r = i;
      } else if (ind == l) {
        l = i;
      }

      forn (j, toAdd.size()) {
        visited[toAdd[j]] = true;
      }

      if (l == 0 && non0 == -1) {
        non0 = toAdd.back();
      }
      // cout << i << " > " << l << " " << r << endl;
      if (l == 0) {
        tmex[i] = (child[l] - child[non0]) * (child[r] + 1);
      } else {
        tmex[i] = (child[l] + 1) * (child[r] + 1);
      }
    }

    forn (i, n + 1) {
      if (i == 0) {
        mex[i] = (LL)n * (LL)(n - 1) / 2 - tmex[0];
      } else if (i < n) {
        mex[i] = tmex[i - 1] - tmex[i];
      } else {
        mex[i] = tmex[i - 1];
      }
    }

    forn (i, n + 1) {
      if (i > 0) {
        cout << " ";
      }
      cout << mex[i];
    }
    cout << endl;

    // forn (i, n + 1) {
    //   if (i > 0) {
    //     cout << " ";
    //   }
    //   cout << tmex[i];
    // }
    // cout << endl;
  }

  return 0;
}