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;
typedef long long ll;
#define int ll
const int maxn = 5e5+ 222;
vector<int>G[maxn];

int fa[maxn][33];
int siz[maxn];
int dep[maxn];
void dfs(int s, int f){
    fa[s][0] = f;
    siz[s] = 1;
    dep[s] = dep[f] + 1;
    for(int i = 1; i < 33; i++){
        fa[s][i] = fa[fa[s][i - 1]][i - 1];
    }
    for(int d : G[s]){
        if(d == f)
            continue;
        dfs(d, s);
        siz[s] += siz[d];
    }
}
int getfa(int x, int d){
    for(int i = 30; i >= 0; i--){
        if(dep[fa[x][i]] >= d)
            x = fa[x][i];
    }
    return x;
}

int n, m;
ll ans[maxn];
int in[maxn];

void solve(){
    int n;
    scanf("%lld", &n);
    for(int i = 0; i < n + 10; i++){
        G[i].clear();
        ans[i] = 0;
        in[i] = 0;
    }
    for(int i = 1; i < n; i++){
        int a, b;
        scanf("%lld %lld", &a, &b);
        G[a].push_back(b);
        G[b].push_back(a);
    }
    dep[0] = -1;
    dfs(0, 0);
    for(int d : G[0]){
        ans[0] += 1ll * siz[d] * (siz[d] - 1) / 2;
    }
    int nowson = getfa(1, 1);
    int sum = 1;
    vector<int>v;
    v.push_back(1);
    for(int d : G[0]){
        if(d == nowson)
            v.push_back(siz[d] - siz[1]);
        else
            v.push_back(siz[d]);
        sum += v.back();
    }
    for(int a : v)
        ans[1] += 1ll * a * (sum - a);
    ans[1] /= 2;

    siz[0] -= siz[nowson];
    //duan dian
    int son[2];
    son[0] = 0;
    son[1] = 1;
    in[0] = 1;
    int nowid = 1;
    while(!in[nowid]){
        in[nowid] = 1;
        nowid = fa[nowid][0];
    }

    for(int i = 2; i <= n; i++){
        if(i == n){
            ans[i] = 1;
            break;
        }
        if(in[i]){
            ans[i] = 0;
            continue;
        }
        //son1 的yan chang
        if(getfa(i, dep[son[1]]) == son[1]){
            ans[i] = 1ll * (siz[son[0]]) * (siz[son[1]] - siz[i]);
            nowid = i;
            while(!in[nowid]){
                in[nowid] = 1;
                nowid = fa[nowid][0];
            }
            son[1] = i;
        }
        else if(getfa(i, dep[son[0]]) == son[0]){
            if(son[0] == 0 && getfa(i, 1) == getfa(1, 1)){
                ans[i] = 1ll * (siz[son[0]]) * (siz[son[1]]);
                break;
            }
            ans[i] = 1ll * (siz[son[0]] - siz[i]) * (siz[son[1]]);
            nowid = i;
            while(!in[nowid]){
                in[nowid] = 1;
                nowid = fa[nowid][0];
            }
            son[0] = i;
        }
        else{
            ans[i] = 1ll * (siz[son[0]]) * (siz[son[1]]);
            break;
        }
    }
    for(int i =0 ; i <= n; i++){
        printf("%lld ", ans[i]);
    }
    puts("");
}
signed main(){
   // freopen("in.txt", "r", stdin);
    int T = 1;
    cin>>T;
    while(T--)
        solve();
}