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>
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
using namespace std;

typedef long long ll;
typedef unsigned long long llu;
typedef pair<int, int> pii;
typedef pair<double, double> pdd;
typedef pair<int, pii> piii;
typedef pair<ll, ll> pll;
typedef pair<ll, int> pli;
typedef pair<int, ll> pil;
typedef pair<string, int> psi;
typedef pair<char, int> pci;
typedef pair<int, char> pic;
const int MOD = 1e9 + 7;
const long double PI = 3.141592653589793238462643383279502884197;

ll fac[1] = {1}, inv[1] = {1};
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll mp(ll a,ll b){ll ret=1;while(b){if(b&1)ret=ret*a%MOD;a=a*a%MOD;b>>=1;}return ret;}
ll cmb(ll r, ll c) {return (c>r||c<0) ? 0:fac[r] * inv[c] % MOD * inv[r - c] % MOD;}

vector<int> v[200005];
int dist[200005];
int spa[200005][18];
ll rotn[200005];
ll ans[200005];


ll go(int o, int pa, int di) {
    dist[o] = di;
    spa[o][0] = pa;

    ll ret = 1;
    for (int i = 1; i < 18; i++) spa[o][i] = spa[spa[o][i-1]][i-1];

    for (int i : v[o]) {
        if (i == pa) continue;
        ll t = go(i, o, di + 1);
        if (o == 0) ans[1] += t * ret;
        ret += t;
    }

    return rotn[o] = ret;
}

int lca(int a, int b) {
    if (dist[a] > dist[b]) swap(a, b);
    for (int i = 17; i >= 0; i--) {
        if (dist[a] <= dist[spa[b][i]])
            b = spa[b][i];
    }
    if (a == b) return a;
    for (int i = 17; i >= 0; i--) {
        if (spa[a][i] != spa[b][i])
            a = spa[a][i], b = spa[b][i];
    }
    return spa[a][0];
}

int lllc(int b) {
    for (int i = 17; i >= 0; i--)
        if (dist[spa[b][i]] > 0)
            b = spa[b][i];
    return b;
}

int main() {
    int tc;
    scanf("%d", &tc);

    while (tc--) {
        int n;
        scanf("%d", &n);

        for (int i = 0; i <= n + 1; i++) v[i].clear(), ans[i] = 0;
        for (int i = 0; i < n - 1; i++) {
            int a, b;
            scanf("%d %d", &a, &b);
            v[a].push_back(b);
            v[b].push_back(a);
        }

        ans[0] = n * (n - 1LL) / 2;
        go(0, 0, 0);

        // 아. 갈고리 모양 뺴줘야 하네?

        int le = 0, ri = 0;
        for (int i = 1; i < n; i++) {
            int t = i;
            int lt = lca(t, le);
            int rt = lca(t, ri);

            if (t == lt || t == rt);
            else if (lt == le) le = t;
            else if (rt == ri && lt == 0) ri = t;
            else break;

            if (ri == 0) ans[i + 1] = rotn[le] * (n - rotn[lllc(le)]);
            else ans[i + 1] = rotn[le] * rotn[ri];
        }

        for (int i = 0; i <= n; i++) printf("%lld ", ans[i] - ans[i + 1]);
        printf("\n");
    }
}

// author: rdd6584