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:
/** Nguyen Anh Tu **/
#include <bits/stdc++.h>
#define maxn 200005
#define maxc 1000000007
#define MOD 1000000007
#define task ""
#define mp make_pair
#define pb push_back
#define ep emplace_back
#define F first
#define S second
#define pii pair<int,int>
#define ll long long
#define bit(p,x) ((x>>p) & 1)
#define remain(a,b) (a+b >= MOD) ? (a+b - MOD) : (a+b)
#define mid ((l + r)/2)
#define Time   cerr << "Time collapse : " << fixed << setprecision(3) << 1.000*clock()/CLOCKS_PER_SEC

using namespace std;

int n;
ll f[maxn], d[maxn];
int par[maxn][19], h[maxn];
vector<int> a[maxn];

void dfs(int u){
    d[u] = 1;
    for(int i = 1; i <= 18; ++ i) par[u][i] = par[par[u][i - 1]][i - 1];
    for(auto v: a[u]) if(v != par[u][0]){
        par[v][0] = u;
        h[v] = h[u] + 1;
        dfs(v);
        d[u] += d[v];
    }
}

int LCA(int u, int v){
    if(h[u] < h[v]) swap(u, v);
    int delta = h[u] - h[v];
    for(int i = 18; i >= 0; -- i) if(bit(i, delta)) u = par[u][i];
    if(u == v) return u;
    for(int i = 18; i >= 0; -- i) if(par[u][i] != par[v][i]){
        u = par[u][i];
        v = par[v][i];
    }
    return par[u][0];
}

bool check(int u, int v, int w){
    int lca = LCA(u, v);
    int lca1 = LCA(u, w);
    return (lca1 == 1 && (lca == u || lca == v));
}

void Solve(){
    cin >> n;
    for(int i = 1; i <= n + 1; ++ i) {
        a[i].clear();
        d[i] = 0;
        f[i] = 0;
        h[i] = 0;
        for(int j = 0; j <= 18; ++ j) par[i][j] = 0;
    }
    for(int i = 1; i < n; ++ i){
        int u, v;
        cin >> u >> v;
        ++ u, ++ v;
        a[u].pb(v);
        a[v].pb(u);
    }
    dfs(1);
    ll s = 0;
    for(auto x: a[1]) {
        f[1] += d[x] * (d[x] - 1) / 2;
        s += d[x];
    }
    ll res, l = 1, r = 1;
    for(auto x: a[1]){
        if(LCA(x, 2) == x){
            s -= d[x];
            for(auto y: a[1]) if(y != x){
                f[2] += d[y] * (s - d[y]);
            }
            f[2] /= 2;
            res = d[1] - d[x];
            f[2] += (d[x] - d[2] + 1) * res - 1;
            l = 2;
            break;
        }
    }
    bool ok = 1;
    for(int i = 3; i <= n; ++ i){
        if(!ok) {
            f[i] = 0;
            continue;
        }
        if(check(i, l, r)){
            if(h[i] > h[l]){
                f[i] = (d[l] - d[i]) * res;
//                if(f[i] == 199998){
//                    cout << l << ' ' << i << ' ' << d[l] << ' ' << d[i] << '\n';
//                }
                l = i;
            }
            else f[i] = 0;
            continue;
        }
        if(check(i, r, l)){
            if(h[i] > h[r]){
                if(r == 1){
                    f[i] = d[l] * (s - d[i] + 1);
                }
                else{
                    f[i] = (d[r] - d[i]) * d[l];
                }
                r = i;
                res = d[i];
            }
            else f[i] = 0;
            continue;
        }
        if(r == 1){
            f[i] = res * d[l];
        }
        else f[i] = d[r] * d[l];
        ok = 0;
    }
    if(ok){
        if(r == 1){
            f[n + 1] = res * d[l];
        }
        else f[n + 1] = d[r] * d[l];
    }
    for(int i = 1; i <= n + 1; ++ i) cout << f[i] << ' ';
    cout << '\n';
}

int main(){
    ios_base::sync_with_stdio(NULL); cin.tie(NULL); cout.tie(NULL);
    if(fopen(task".inp","r")){
        freopen(task".inp","r",stdin);
        freopen(task".out","w",stdout);
    }
    int t;
    cin >> t;
    while(t --){
        Solve();
    }
    Time;
    return 0;
}