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;

const int maxn = 4e5 + 233;
int f[maxn][21];
vector<int> G[maxn];
int n, T;
typedef long long ll;
int sz[maxn];
int d[maxn];

void dfs(int u, int fa){
    sz[u] = 1;
    f[u][0] = fa;
    d[u] = d[fa] + 1;
    for (int i = 1; i <= 20; i += 1){
        f[u][i] = f[f[u][i - 1]][i - 1];
    }
    for(auto v : G[u]){
        if(v == fa) continue;
        dfs(v, u);
        sz[u] += sz[v];
    }
}

int lca(int x, int y){
    if(d[x] > d[y]) swap(x, y);
    for(int i = 20; i >= 0; i -= 1){
        if(d[f[y][i]] >= d[x]) y = f[y][i];
    }
    if(x == y) return x;
    for(int i = 20; i >= 0; i -= 1){
        if(f[x][i] != f[y][i]) x = f[x][i], y = f[y][i];
    }
    return f[x][0];
}

int get(int x, int y){
    if(d[x] > d[y]) swap(x, y);
    for(int i = 20; i >= 0; i -= 1){
        if(d[f[y][i]] > d[x]) y = f[y][i]; 
    }
    return y;
}

bool ispar(int x, int y){
    int lc = lca(x, y);
    if(lc == x || lc == y) return true;
    return false;
}

ll cal(int x, int y){
    if(d[x] > d[y]) swap(x, y);
    if(ispar(x, y)) {
        return 1ll * (n - sz[get(x, y)]) * sz[y];
    }
    return 1ll * sz[x] * sz[y];
}

ll res[maxn];

int main(){
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> T;
    while(T--){
        cin >> n;
        for (int i = 1; i <= n; i += 1){
            G[i].clear();
            res[i] = 0;
        }
        for (int i = 1; i < n; i += 1){
            int u, v;
            cin >> u >> v;
            u += 1;
            v += 1;
            G[u].emplace_back(v);
            G[v].emplace_back(u);
        }
        dfs(1, 0);
        int p[2] = {1, 2};
        {
            ll tmp = 1;
            for(auto u : G[1]){
                res[1] += tmp * sz[u];
                tmp += sz[u];
            }
        }
        
        res[2] += cal(p[0], p[1]);
        res[1] -= cal(p[0], p[1]);

        for(int i = 3; i <= n; i += 1){
            if(d[p[0]] < d[p[1]]) swap(p[0], p[1]);
            if(ispar(i, p[0]) && ispar(i, p[1])){
                if(d[p[0]] < d[i]) p[0] = i;
            }
            else if(ispar(i, p[0])){
                if(d[p[0]] < d[i]) p[0] = i;
            }
            else if(ispar(i, p[1]) && (!ispar(p[0], p[1]) || lca(i, p[0]) == p[1])){
                if(d[p[1]] < d[i]) p[1] = i;
            }
            else{
                break;
            }
            res[i] += cal(p[0], p[1]);
            res[i - 1] -= cal(p[0], p[1]);
        }
        res[0] = 1ll * n * (n - 1) / 2;
        for(int i = 1; i <= n; i += 1){
            res[0] -= res[i];
        }
        for (int i = 0; i <= n; i += 1){
            cout << res[i] << " \n"[i == n];
        }
    }
    return 0;
}