#include<bits/stdc++.h>
using namespace std;
#define ll long long int 
#define pb push_back
#define ff first
#define ss second
#define pi pair<int,int>
#define INF 1e18
#define db double 
#define vec vector<ll>
#define test cout<<" test_rounds"<<endl
#define ull unsigned long long int 
#define cntone(n)  __builtin_popcount(n)
#define fastio  ios_base::sync_with_stdio(false),cin.tie(NULL)
#define pai acos(-1.0)
#define mod 1000000007
#define dbl long double
#define mk make_pair(ll,ll)
#define mem(a,b) memset(a,b,sizeof(a))
#define sz(s) int(s.size())
#define min3(a,b,c) min(a,min(b,c))
#define max3(a,b,c) max(a,max(b,c))


const int mxx=2e5+2;
int intime[mxx],outime[mxx],le[mxx],hi[mxx];
int up[mxx][18];

vector<int>v[mxx];

ll pre[mxx],ans[mxx];
int tme =0;
ll dfs(int p,int n,int d,int ned){

    intime[n]=++tme;
    le[n]=d;
    ll x=0;
    up[n][0]=p;

    for(int i=1;i<=17;i++){
        up[n][i]=up[up[n][i-1]][i-1];
    }

    for(auto it:v[n]){
        if(n==0)
        {if(it!=p)x+=dfs(n,it,d+1,it);}
        else {if(it!=p)x+=dfs(n,it,d+1,ned);}
    }

    outime[n]=tme;
    pre[n]=x;
    hi[n]=ned;
    if(p==0)hi[n]=n;
    return x+1;
}

int lca(int a,int b){
    if(le[a]<le[b])swap(a,b);
    int x=le[a]-le[b];
    for(int i=17;i>=0;i--){
        if((1<<i)&x){
            a=up[a][i];
        }
    }
    if(a==b)return a;
    for(int i=17;i>=0;i--){

        if(up[a][i]!=up[b][i]){
            a=up[a][i];
            b=up[b][i];
        }
    }
    return up[a][0];
}

int main()
{   
   int t;
   scanf("%d",&t);
    while(t--)
    {
          int n;
          scanf("%d",&n);
          for(int i=1;i<n;i++) {
             int a,b;
             scanf("%d%d",&a,&b);
             v[a].pb(b);
             v[b].pb(a);
          }
          ll x=dfs(0,0,1,0);
          for(auto it:v[0]){
            ll x=pre[it];
            ans[0]+=x*(x+1)/2;
          }
          int l=0,r=0;
          bool chk=0;
          tme=0;
          for(int i=1;i<n;i++)
         {      
            if(le[l]>le[r])swap(l,r);

            if(l==r) 
            {
                     
                     ll y=0;
                    
                     ll x=pre[hi[1]]-pre[1]+1;

                     ll sum=pre[0]-pre[hi[1]];
                     ll tot=0;
                     //cout<<x<<" "<<sum<<endl;
                     ans[i]+=(x-1)*sum+sum-1;
                     tot=sum-1;
                     for(auto it:v[0])
                     {
                        if(intime[1]>=intime[it] and outime[1]<=outime[it]){
                            continue;
                        }
                        else {
                               ll t=pre[it]+1;
                               if(tot-t>0)ans[i]+=t*(tot-t);
                               tot-=t;
                             }
                     }

                     
                     l=0;
                     r=1;
                     continue;
            } 
            //   if the bound lies  between the curve //
            if(intime[l]>=intime[i] and outime[l]<=outime[i] ||intime[r]>=intime[i] and outime[r]<=outime[i])
            continue;
            
           else if(intime[i]>=intime[r] and outime[i]<=outime[r])
           {
                    ll x,y=1;
                    
                    x=pre[r]-(pre[i]+1)+1;
                    
                    if(intime[r]>=intime[l] and outime[r]<=outime[l]){
                              
                              y=pre[l]-pre[hi[r]];
                    }
                    else y=pre[l]+1;
                    ans[i]=x*y;
                 //   cout<<" answer "<<ans[i]<<endl;
                    r=i;
          }
          else if(intime[i]>=intime[l] and outime[i]<=outime[l])
           {
                   
                   ll x=pre[r]+1;
                   ll y=1;
                   //cout<<l<<" "<<r<<endl;
                   if(intime[r]>=intime[l] and outime[r]<=outime[l])
                   {  
                       
                        int k=lca(r,i);
                        if(k!=l){chk=1;}
                         if(hi[r]==hi[i]){
                            y=pre[l]-pre[hi[r]];
                         }
                         else y=pre[l]-(pre[hi[r]]+pre[i])-1;

                    }
                    else y=pre[l]-pre[i];
                
                    ans[i]=x*y;
                    l=i;
            }
             else {
                  chk=1;
                  ans[i]=(pre[r]+1)*(pre[l]+1);

             }
             if(chk)break; 
          }
          for(int i=0;i<=n;i++){
            if(i==n and chk==0)ans[i]=1;
            printf("%lld ",ans[i]);
            ans[i]=0;
            v[i].clear();
          }
          printf("\n");

    }
} 

### Prompt

Please create a solution in Cpp 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;
#define ll long long int 
#define pb push_back
#define ff first
#define ss second
#define pi pair<int,int>
#define INF 1e18
#define db double 
#define vec vector<ll>
#define test cout<<" test_rounds"<<endl
#define ull unsigned long long int 
#define cntone(n)  __builtin_popcount(n)
#define fastio  ios_base::sync_with_stdio(false),cin.tie(NULL)
#define pai acos(-1.0)
#define mod 1000000007
#define dbl long double
#define mk make_pair(ll,ll)
#define mem(a,b) memset(a,b,sizeof(a))
#define sz(s) int(s.size())
#define min3(a,b,c) min(a,min(b,c))
#define max3(a,b,c) max(a,max(b,c))


const int mxx=2e5+2;
int intime[mxx],outime[mxx],le[mxx],hi[mxx];
int up[mxx][18];

vector<int>v[mxx];

ll pre[mxx],ans[mxx];
int tme =0;
ll dfs(int p,int n,int d,int ned){

    intime[n]=++tme;
    le[n]=d;
    ll x=0;
    up[n][0]=p;

    for(int i=1;i<=17;i++){
        up[n][i]=up[up[n][i-1]][i-1];
    }

    for(auto it:v[n]){
        if(n==0)
        {if(it!=p)x+=dfs(n,it,d+1,it);}
        else {if(it!=p)x+=dfs(n,it,d+1,ned);}
    }

    outime[n]=tme;
    pre[n]=x;
    hi[n]=ned;
    if(p==0)hi[n]=n;
    return x+1;
}

int lca(int a,int b){
    if(le[a]<le[b])swap(a,b);
    int x=le[a]-le[b];
    for(int i=17;i>=0;i--){
        if((1<<i)&x){
            a=up[a][i];
        }
    }
    if(a==b)return a;
    for(int i=17;i>=0;i--){

        if(up[a][i]!=up[b][i]){
            a=up[a][i];
            b=up[b][i];
        }
    }
    return up[a][0];
}

int main()
{   
   int t;
   scanf("%d",&t);
    while(t--)
    {
          int n;
          scanf("%d",&n);
          for(int i=1;i<n;i++) {
             int a,b;
             scanf("%d%d",&a,&b);
             v[a].pb(b);
             v[b].pb(a);
          }
          ll x=dfs(0,0,1,0);
          for(auto it:v[0]){
            ll x=pre[it];
            ans[0]+=x*(x+1)/2;
          }
          int l=0,r=0;
          bool chk=0;
          tme=0;
          for(int i=1;i<n;i++)
         {      
            if(le[l]>le[r])swap(l,r);

            if(l==r) 
            {
                     
                     ll y=0;
                    
                     ll x=pre[hi[1]]-pre[1]+1;

                     ll sum=pre[0]-pre[hi[1]];
                     ll tot=0;
                     //cout<<x<<" "<<sum<<endl;
                     ans[i]+=(x-1)*sum+sum-1;
                     tot=sum-1;
                     for(auto it:v[0])
                     {
                        if(intime[1]>=intime[it] and outime[1]<=outime[it]){
                            continue;
                        }
                        else {
                               ll t=pre[it]+1;
                               if(tot-t>0)ans[i]+=t*(tot-t);
                               tot-=t;
                             }
                     }

                     
                     l=0;
                     r=1;
                     continue;
            } 
            //   if the bound lies  between the curve //
            if(intime[l]>=intime[i] and outime[l]<=outime[i] ||intime[r]>=intime[i] and outime[r]<=outime[i])
            continue;
            
           else if(intime[i]>=intime[r] and outime[i]<=outime[r])
           {
                    ll x,y=1;
                    
                    x=pre[r]-(pre[i]+1)+1;
                    
                    if(intime[r]>=intime[l] and outime[r]<=outime[l]){
                              
                              y=pre[l]-pre[hi[r]];
                    }
                    else y=pre[l]+1;
                    ans[i]=x*y;
                 //   cout<<" answer "<<ans[i]<<endl;
                    r=i;
          }
          else if(intime[i]>=intime[l] and outime[i]<=outime[l])
           {
                   
                   ll x=pre[r]+1;
                   ll y=1;
                   //cout<<l<<" "<<r<<endl;
                   if(intime[r]>=intime[l] and outime[r]<=outime[l])
                   {  
                       
                        int k=lca(r,i);
                        if(k!=l){chk=1;}
                         if(hi[r]==hi[i]){
                            y=pre[l]-pre[hi[r]];
                         }
                         else y=pre[l]-(pre[hi[r]]+pre[i])-1;

                    }
                    else y=pre[l]-pre[i];
                
                    ans[i]=x*y;
                    l=i;
            }
             else {
                  chk=1;
                  ans[i]=(pre[r]+1)*(pre[l]+1);

             }
             if(chk)break; 
          }
          for(int i=0;i<=n;i++){
            if(i==n and chk==0)ans[i]=1;
            printf("%lld ",ans[i]);
            ans[i]=0;
            v[i].clear();
          }
          printf("\n");

    }
} 

```