#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=250005;
vector<int> e[N];
int fa[N][20],dep[N],sz[N];
long long ans[N];
void dfs(int u,int fath){
    fa[u][0]=fath; sz[u]=1;
    for(int i=1;i<19;++i)
        fa[u][i]=fa[fa[u][i-1]][i-1];
    for(int v:e[u])
        if(v!=fath) dep[v]=dep[u]+1,dfs(v,u),sz[u]+=sz[v];
}
int LCA(int u,int v){
    if(dep[u]<dep[v]) swap(u,v);
    for(int i=18;i>=0;--i)
        if(dep[fa[u][i]]>=dep[v]) u=fa[u][i];
    if(u==v) return u;
    for(int i=18;i>=0;--i)
        if(fa[u][i]!=fa[v][i]) u=fa[u][i],v=fa[v][i];
    return fa[u][0];
}
int get(int u,int l){
    for(int i=18;i>=0;--i)
        if(dep[fa[u][i]]>dep[l]) u=fa[u][i];
    return u;
}
int dis(int u,int v){
    return dep[u]+dep[v]-2*dep[LCA(u,v)];
}
int n;
ll calc(int u,int v){
    int l=LCA(u,v);
    if(u==l) return 1ll*sz[v]*(n-sz[get(v,l)]);
    if(v==l) return 1ll*sz[u]*(n-sz[get(u,l)]);
    return 1ll*sz[u]*sz[v];
}
void solve(){
    cin>>n;
    for(int i=1;i<=n;++i) e[i].clear();
    for(int i=1;i<n;++i){
        int u,v;
        cin>>u>>v;++u,++v;
        e[u].push_back(v),e[v].push_back(u);
    }
    dep[1]=1;
    dfs(1,0);
    //for(int i=1;i<=n;++i) cout<<dep[i]<<" ";cout<<endl;
    int u=1,v=1;
    long long sum=1;ans[1]=0;
    for(int v:e[1])
        ans[1]+=1ll*sz[v]*sum,sum+=sz[v];
    ans[n+1]=0;
    for(int i=2;i<=n;++i) ans[i]=0;
    for(int i=1;i<=n;++i){
        if(i!=1) ans[i]=calc(u,v);
        if(dis(u,i+1)+dis(u,v)==dis(i+1,v)) u=i+1;
        else if(dis(v,i+1)+dis(u,v)==dis(i+1,u)) v=i+1;
        else if(dis(u,i+1)+dis(i+1,v)!=dis(u,v)) break;
    }
    sum=0;
    //for(int i=1;i<=n;++i) cout<<ans[i]<<" ";cout<<"\n";
    for(int i=n;i>=1;--i) sum+=ans[i]-ans[i+1];
    cout<<1ll*n*(n-1)/2-sum<<" ";
    for(int i=1;i<=n;++i)
        cout<<ans[i]-ans[i+1]<<" ";
    cout<<"\n";
}
signed main(){
    ios::sync_with_stdio(false);
    int T;cin>>T;while(T--)solve();return 0;
}

### Prompt

Generate a cpp solution to the following 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. 

### Response

```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=250005;
vector<int> e[N];
int fa[N][20],dep[N],sz[N];
long long ans[N];
void dfs(int u,int fath){
    fa[u][0]=fath; sz[u]=1;
    for(int i=1;i<19;++i)
        fa[u][i]=fa[fa[u][i-1]][i-1];
    for(int v:e[u])
        if(v!=fath) dep[v]=dep[u]+1,dfs(v,u),sz[u]+=sz[v];
}
int LCA(int u,int v){
    if(dep[u]<dep[v]) swap(u,v);
    for(int i=18;i>=0;--i)
        if(dep[fa[u][i]]>=dep[v]) u=fa[u][i];
    if(u==v) return u;
    for(int i=18;i>=0;--i)
        if(fa[u][i]!=fa[v][i]) u=fa[u][i],v=fa[v][i];
    return fa[u][0];
}
int get(int u,int l){
    for(int i=18;i>=0;--i)
        if(dep[fa[u][i]]>dep[l]) u=fa[u][i];
    return u;
}
int dis(int u,int v){
    return dep[u]+dep[v]-2*dep[LCA(u,v)];
}
int n;
ll calc(int u,int v){
    int l=LCA(u,v);
    if(u==l) return 1ll*sz[v]*(n-sz[get(v,l)]);
    if(v==l) return 1ll*sz[u]*(n-sz[get(u,l)]);
    return 1ll*sz[u]*sz[v];
}
void solve(){
    cin>>n;
    for(int i=1;i<=n;++i) e[i].clear();
    for(int i=1;i<n;++i){
        int u,v;
        cin>>u>>v;++u,++v;
        e[u].push_back(v),e[v].push_back(u);
    }
    dep[1]=1;
    dfs(1,0);
    //for(int i=1;i<=n;++i) cout<<dep[i]<<" ";cout<<endl;
    int u=1,v=1;
    long long sum=1;ans[1]=0;
    for(int v:e[1])
        ans[1]+=1ll*sz[v]*sum,sum+=sz[v];
    ans[n+1]=0;
    for(int i=2;i<=n;++i) ans[i]=0;
    for(int i=1;i<=n;++i){
        if(i!=1) ans[i]=calc(u,v);
        if(dis(u,i+1)+dis(u,v)==dis(i+1,v)) u=i+1;
        else if(dis(v,i+1)+dis(u,v)==dis(i+1,u)) v=i+1;
        else if(dis(u,i+1)+dis(i+1,v)!=dis(u,v)) break;
    }
    sum=0;
    //for(int i=1;i<=n;++i) cout<<ans[i]<<" ";cout<<"\n";
    for(int i=n;i>=1;--i) sum+=ans[i]-ans[i+1];
    cout<<1ll*n*(n-1)/2-sum<<" ";
    for(int i=1;i<=n;++i)
        cout<<ans[i]-ans[i+1]<<" ";
    cout<<"\n";
}
signed main(){
    ios::sync_with_stdio(false);
    int T;cin>>T;while(T--)solve();return 0;
}

```