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

vector<int>adj[(int)2e5+1];
vector<int>sz((int)2e5+1);
vector<int>mini((int)2e5+1,1e9);
vector<ll>ans((int)2e5+1);
vector<int>parent((int)2e5+1);
vector<int>s((int)2e5+1);

void dfs(int x,int p)
{
    parent[x]=p;   
    for(auto i:adj[x]) 
    if(i!=p) dfs(i,x);
    for(auto i:adj[x]) 
    if(i!=p) 
    {
        sz[x]+=sz[i]+1;
        mini[x]=min(mini[x],min(mini[i],i));
    }
}
void rm(int x)
{
   // cout<<"rm "<<x<<"\n";
    // if(s.count(x)==0) return;
    // s.erase(x);
    // rm(parent[x]);
    if(s[x]==0) return;
    s[x]=0;rm(parent[x]);
}

void fun()
{
    int n;cin>>n;//s.clear();
    for(int i=0;i<n+1;i++)
    {
        s[i]=1;
        //s.insert(i);
        adj[i].clear();
        sz[i]=0;
        parent[i]=0;
        ans[i]=0;
        mini[i]=1e9;
    }
    for(int i=0;i<n-1;i++)
    {
        int x,y;cin>>x>>y;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    dfs(0,0);
    if(n==2){cout<<0<<" "<<0<<" "<<1;return;}
    for(auto i:adj[0])
    {
        //cout<<sz[i]<<" ";
        ans[0]+=((ll)(sz[i]+1)*(ll)(sz[i]))/2;
    }   
   // cout<<"\n";
    int l=0;
    int r=0;
    //s.erase(0);
    s[0]=0;
    vector<int>v;
    for(auto i:adj[0]) 
    if(mini[i]==1||i==1) v.push_back(sz[i]-sz[1]);
    else v.push_back(sz[i]+1);
    for(auto i:v) ans[1]+=i;
    for(int i=v.size()-2;i>=0;i--)
    {
        ans[1]+=(ll)v[i]*(ll)v[i+1];
        v[i]+=v[i+1];
    }
    rm(1);
    r=1;
   // sz[0]-=sz[1]+1;

    int curr=1;
    while(parent[curr]!=0) curr=parent[curr];
    sz[0]-=sz[curr]+1;
    
    int minl=1e9;
    for(auto i:adj[l])
    {
        if(s[i]==0) continue;
        minl=min(minl,mini[i]);
        minl=min(minl,i);
    }
    int minr=1e9;
    for(auto i:adj[r])
    {
        if(s[i]==0) continue;
        minr=min(minr,mini[i]);
        minr=min(minr,i);

    }
    for(int i=2;i<=n;i++)
    {
        if(s[i]==0) continue;
        int x=i;//cout<<x<<"\n";
        
        //cout<<x<<" "<<minl<<" "<<minr<<"\n";
        if(minl==x)
        {
            ans[x]+=(ll)(sz[l]-sz[x])*(ll)(sz[r]+1);
            //ans[x]++;
            l=x;
            rm(x);minl=1e9;
            for(auto i:adj[l])
            {
            if(s[i]==0) continue;
            minl=min(minl,mini[i]);
            minl=min(minl,i);
            }
        }
        else if(minr==x)
        {
            ans[x]+=(ll)(sz[r]-sz[x])*(ll)(sz[l]+1);
            //ans[x]++;
            r=x;
            rm(x);minr=1e9;
            for(auto i:adj[r])
            {
            if(s[i]==0) continue;
            minr=min(minr,mini[i]);
            minr=min(minr,i);

            }

        }
        else 
        {
            //ans[x]=1;
            ans[x]=(ll)(sz[l]+1)*(ll)(sz[r]+1);
            break;
        }
        //for(auto i:s) cout<<i<<" ";
        //cout<<"\n";
    
    }
   // if(ans[n-1]!=0) ans[n]++;
    
    
    for(int i=0;i<n+1;i++) cout<<ans[i]<<" ";

}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;cin>>t;
    while(t--)
    {
        fun();
        cout<<"\n";
    }
}
### Prompt

Your task is to create 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;
#define ll long long

vector<int>adj[(int)2e5+1];
vector<int>sz((int)2e5+1);
vector<int>mini((int)2e5+1,1e9);
vector<ll>ans((int)2e5+1);
vector<int>parent((int)2e5+1);
vector<int>s((int)2e5+1);

void dfs(int x,int p)
{
    parent[x]=p;   
    for(auto i:adj[x]) 
    if(i!=p) dfs(i,x);
    for(auto i:adj[x]) 
    if(i!=p) 
    {
        sz[x]+=sz[i]+1;
        mini[x]=min(mini[x],min(mini[i],i));
    }
}
void rm(int x)
{
   // cout<<"rm "<<x<<"\n";
    // if(s.count(x)==0) return;
    // s.erase(x);
    // rm(parent[x]);
    if(s[x]==0) return;
    s[x]=0;rm(parent[x]);
}

void fun()
{
    int n;cin>>n;//s.clear();
    for(int i=0;i<n+1;i++)
    {
        s[i]=1;
        //s.insert(i);
        adj[i].clear();
        sz[i]=0;
        parent[i]=0;
        ans[i]=0;
        mini[i]=1e9;
    }
    for(int i=0;i<n-1;i++)
    {
        int x,y;cin>>x>>y;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    dfs(0,0);
    if(n==2){cout<<0<<" "<<0<<" "<<1;return;}
    for(auto i:adj[0])
    {
        //cout<<sz[i]<<" ";
        ans[0]+=((ll)(sz[i]+1)*(ll)(sz[i]))/2;
    }   
   // cout<<"\n";
    int l=0;
    int r=0;
    //s.erase(0);
    s[0]=0;
    vector<int>v;
    for(auto i:adj[0]) 
    if(mini[i]==1||i==1) v.push_back(sz[i]-sz[1]);
    else v.push_back(sz[i]+1);
    for(auto i:v) ans[1]+=i;
    for(int i=v.size()-2;i>=0;i--)
    {
        ans[1]+=(ll)v[i]*(ll)v[i+1];
        v[i]+=v[i+1];
    }
    rm(1);
    r=1;
   // sz[0]-=sz[1]+1;

    int curr=1;
    while(parent[curr]!=0) curr=parent[curr];
    sz[0]-=sz[curr]+1;
    
    int minl=1e9;
    for(auto i:adj[l])
    {
        if(s[i]==0) continue;
        minl=min(minl,mini[i]);
        minl=min(minl,i);
    }
    int minr=1e9;
    for(auto i:adj[r])
    {
        if(s[i]==0) continue;
        minr=min(minr,mini[i]);
        minr=min(minr,i);

    }
    for(int i=2;i<=n;i++)
    {
        if(s[i]==0) continue;
        int x=i;//cout<<x<<"\n";
        
        //cout<<x<<" "<<minl<<" "<<minr<<"\n";
        if(minl==x)
        {
            ans[x]+=(ll)(sz[l]-sz[x])*(ll)(sz[r]+1);
            //ans[x]++;
            l=x;
            rm(x);minl=1e9;
            for(auto i:adj[l])
            {
            if(s[i]==0) continue;
            minl=min(minl,mini[i]);
            minl=min(minl,i);
            }
        }
        else if(minr==x)
        {
            ans[x]+=(ll)(sz[r]-sz[x])*(ll)(sz[l]+1);
            //ans[x]++;
            r=x;
            rm(x);minr=1e9;
            for(auto i:adj[r])
            {
            if(s[i]==0) continue;
            minr=min(minr,mini[i]);
            minr=min(minr,i);

            }

        }
        else 
        {
            //ans[x]=1;
            ans[x]=(ll)(sz[l]+1)*(ll)(sz[r]+1);
            break;
        }
        //for(auto i:s) cout<<i<<" ";
        //cout<<"\n";
    
    }
   // if(ans[n-1]!=0) ans[n]++;
    
    
    for(int i=0;i<n+1;i++) cout<<ans[i]<<" ";

}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;cin>>t;
    while(t--)
    {
        fun();
        cout<<"\n";
    }
}
```