#include<bits/stdc++.h>
using namespace std;

const int N=2e5+10;
set<long long>s[N];

int res;
void dfs1(int u,int f){
     if(u==1) res=f;
     for(auto it : s[u]){
          if(it!=f) dfs1(it,u);
     }
}


int fa[N][22],h[N];
long long siz[N];
void dfs2(int u,int f){
    int i;
    if(f!=-1){
        fa[u][0]=f;
        h[u]=h[f]+1;
        for(i=1;i<=19;i++) if(fa[u][i-1]!=-1) fa[u][i]=fa[fa[u][i-1]][i-1];
    }
    else h[u]=0;
    siz[u]=1;
    for(auto it : s[u]){
        if(it!=f){
            dfs2(it,u);
            siz[u]+=siz[it];
        }
    }
}

int lca(int a,int b){
    if(h[a]<h[b]) swap(a,b);
    int i;
    for(i=19;i>=0;i--) if(fa[a][i]!=-1&&h[fa[a][i]]>=h[b]) a=fa[a][i];
    if(a==b) return a;
    for(i=19;i>=0;i--) if(fa[a][i]!=fa[b][i]){
        a=fa[a][i];
        b=fa[b][i];
    }
    return fa[a][0];
}


long long ans[N];

int f(int a,int b,int n,int i,int x){
    return x!=a&&x!=b&&x!=n&&x!=i;
}
int main(){
     long long n,i,a,b,c,d,t;
     cin>>t;
     while(t--){
         cin>>n;
         for(i=0;i<=n;i++){
            memset(fa[i],-1,sizeof(fa[i]));
            ans[i]=0;
            s[i].clear();
         }

         for(i=1;i<n;i++){
            cin>>a>>b;
            s[a].insert(b);
            s[b].insert(a);
         }
         dfs1(0,-1);


         s[res].erase(1);
         s[1].erase(res);

         s[1].insert(n);
         s[n].insert(1);

         s[res].insert(n);
         s[n].insert(res);


         dfs2(n,-1);

         long long x,y,z,cnt=1;
         for(auto it : s[0]){
              if(it!=fa[0][0]) z=x=siz[it];
              else{
              	x=n-siz[0];
              	z=x-siz[1];
              }
              ans[0]+=x*(x-1)/2;
              ans[1]+=z*cnt;
              cnt+=z;
         }


         a=1;
         b=0;
         for(i=2;i<=n;i++){
            if(i!=n){
                c=lca(a,i);
                d=lca(b,i);
                    if(c==a){
                         ans[i]=(siz[a]-siz[i])*siz[b];
                         a=i;
                    }
                    else if(d==b){
                         ans[i]=(siz[b]-siz[i])*siz[a];
                         b=i;
                    }
                    else if(c==i||d==i) ans[i]=0;
                else{
                    ans[i]=siz[a]*siz[b];
                    break;
                }
            }
            else ans[i]=1;
         }
         for(i=0;i<=n;i++) printf("%lld ",ans[i]);
         printf("\n");
    }
}
### Prompt

Construct a cpp code solution to the problem outlined:

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;

const int N=2e5+10;
set<long long>s[N];

int res;
void dfs1(int u,int f){
     if(u==1) res=f;
     for(auto it : s[u]){
          if(it!=f) dfs1(it,u);
     }
}


int fa[N][22],h[N];
long long siz[N];
void dfs2(int u,int f){
    int i;
    if(f!=-1){
        fa[u][0]=f;
        h[u]=h[f]+1;
        for(i=1;i<=19;i++) if(fa[u][i-1]!=-1) fa[u][i]=fa[fa[u][i-1]][i-1];
    }
    else h[u]=0;
    siz[u]=1;
    for(auto it : s[u]){
        if(it!=f){
            dfs2(it,u);
            siz[u]+=siz[it];
        }
    }
}

int lca(int a,int b){
    if(h[a]<h[b]) swap(a,b);
    int i;
    for(i=19;i>=0;i--) if(fa[a][i]!=-1&&h[fa[a][i]]>=h[b]) a=fa[a][i];
    if(a==b) return a;
    for(i=19;i>=0;i--) if(fa[a][i]!=fa[b][i]){
        a=fa[a][i];
        b=fa[b][i];
    }
    return fa[a][0];
}


long long ans[N];

int f(int a,int b,int n,int i,int x){
    return x!=a&&x!=b&&x!=n&&x!=i;
}
int main(){
     long long n,i,a,b,c,d,t;
     cin>>t;
     while(t--){
         cin>>n;
         for(i=0;i<=n;i++){
            memset(fa[i],-1,sizeof(fa[i]));
            ans[i]=0;
            s[i].clear();
         }

         for(i=1;i<n;i++){
            cin>>a>>b;
            s[a].insert(b);
            s[b].insert(a);
         }
         dfs1(0,-1);


         s[res].erase(1);
         s[1].erase(res);

         s[1].insert(n);
         s[n].insert(1);

         s[res].insert(n);
         s[n].insert(res);


         dfs2(n,-1);

         long long x,y,z,cnt=1;
         for(auto it : s[0]){
              if(it!=fa[0][0]) z=x=siz[it];
              else{
              	x=n-siz[0];
              	z=x-siz[1];
              }
              ans[0]+=x*(x-1)/2;
              ans[1]+=z*cnt;
              cnt+=z;
         }


         a=1;
         b=0;
         for(i=2;i<=n;i++){
            if(i!=n){
                c=lca(a,i);
                d=lca(b,i);
                    if(c==a){
                         ans[i]=(siz[a]-siz[i])*siz[b];
                         a=i;
                    }
                    else if(d==b){
                         ans[i]=(siz[b]-siz[i])*siz[a];
                         b=i;
                    }
                    else if(c==i||d==i) ans[i]=0;
                else{
                    ans[i]=siz[a]*siz[b];
                    break;
                }
            }
            else ans[i]=1;
         }
         for(i=0;i<=n;i++) printf("%lld ",ans[i]);
         printf("\n");
    }
}
```