//--------------TTH-----------------
#include <bits/stdc++.h>
#define  HUNGTT "MEX Tree"
#define memset(f,a) memset(f,(a),sizeof(f))
#define forr(i,a,b) for(int i=(a);i<=(b);++i)
#define ford(i,a,b) for(int i=(a);i>=(b);--i)
#define fore(it,a) for(__typeof((a).begin()) it=(a).begin();it!=(a).end();++it)
#define F first
#define S second
#define mp make_pair
#define ALL(a) (a).begin(),(a).end()
#define MASK(i) (1LL<<(i))
#define BIT(x,i) (((x)>>(i))&1)

using namespace std;
mt19937 Rand(time(0));

typedef long long ll ;
typedef long double ld ;
typedef pair<int,int> ii ;

const int MAXN=2e5 ;


int in[MAXN+5],out[MAXN+5] ;
vector<int> adj[MAXN+5] ;
int n,times ;
const int LOG=18 ;
ll ans[MAXN+5] ;
int p[MAXN+5][LOG+2] ;
int bit[MAXN+5],child[MAXN+5] ;
int dep[MAXN+5] ;

void read()
{
    cin>>n ;
    forr(i,1,n)
    {
        adj[i].clear() ;
        in[i]=out[i]=bit[i]=dep[i]=0 ;
        child[i]=0 ;
        forr(x,0,LOG) p[i][x]=0 ;
    }
    forr(i,1,n+1) ans[i]=0 ;
    times=0 ;
    forr(LOVE,1,n-1)
    {
        int u,v ;
        cin>>u >>v ;
        ++u,++v ;
        adj[u].push_back(v) ;
        adj[v].push_back(u) ;
    }

}

void dfs(int u,int par=-1)
{
    in[u]=++times ;
    child[u]=1 ;
    forr(x,1,LOG) p[u][x]=p[p[u][x-1]][x-1] ;
    for(auto v: adj[u])
    {
        if(v==par) continue ;
        p[v][0]=u ;
        dep[v]=dep[u]+1 ;
        dfs(v,u) ;
        child[u]+=child[v] ;
    }
    out[u]=times ;
}

int Jump(int u,int x)
{
    forr(i,0,LOG)
    if(BIT(x,i)) u=p[u][i] ;
    return u ;
}

int LCA(int u,int v)
{
          if(dep[u]<dep[v]) swap(u,v) ;
          u=Jump(u,dep[u]-dep[v]) ;
          if(u==v) return u ;
          ford(x,LOG,0)
          if(p[u][x]!=p[v][x])
                    u=p[u][x],v=p[v][x] ;
          return p[u][0] ;
}

bool isChild(int u,int p)
{
    return in[u]>=in[p] && in[u]<=out[p] ;
}

int get(int x)
{
    int res=0 ;
    for(; x>0; x-=x& -x)
        res+=bit[x] ;
    return res ;
}
void update(int x,int val)
{
    for(; x<=n; x+=x& -x)
        bit[x]+=val ;
}

void solve()
{
    dfs(1) ;
    int Left=1,Right=1 ;
    update(1,1) ;
    int sum=1 ;
    for(auto u : adj[1])
    {
              ans[1]+=1LL*child[u]*(child[u]-1)/2;
              if(isChild(2,u)) ans[2]+=1LL*(child[u]-child[2])*sum ;
              else ans[2]+=1LL*(child[u])*sum ;
              if(isChild(2,u)) sum+=child[u]-child[2];
              else sum+=child[u] ;
    }
    forr(i,2,n+1)
    {
        if(in[Left]>in[Right]) swap(Left,Right) ;
        //cout<<i<<" "<<Left<<" "<<Right<<"\n" ;
        if(get(in[Left])+get(in[Right])-1!=i-1 || LCA(Left,Right)!=1)
        {
                 // if(n==2e5) cout<<"*"<<i<<"\n" ;
                  break ;
        }
        if(i<=n)
        {
            update(in[i],1) ;
            update(out[i]+1,-1) ;
        }
        if(get(in[Left])+get(in[Right])-1==i) continue ;
        if(Left!=Right && !isChild(Left,i) && !isChild(Right,i))
        {
            if(isChild(Right,Left))
            {
                int q=Jump(Right,dep[Right]-1) ;
                if(isChild(i,Right))
                    ans[i]=1LL*(child[Right]-child[i])*(child[1]-child[q]) ;
                else
                {
                    if(isChild(i,q))
                        ans[i]=1LL*(child[Right])*(child[1]-child[q]) ;
                    else ans[i]=1LL*child[Right]*(child[1]-child[q]-child[i]) ;
                }
            }
            else
            {
                if(!isChild(i,Left) && !isChild(i,Right))
                {
                    ans[i]=1LL*child[Left]*child[Right] ;
                }
                else
                {
                    if(isChild(i,Left)) ans[i]=1LL*(child[Left]-child[i])*child[Right] ;
                    else ans[i]=1LL*(child[Left])*(child[Right]-child[i]) ;
                }
            }
        }
        if(isChild(Left,i) || isChild(Right,i)) continue ;
        if(isChild(i,Right)) Right=i ;
        else if(isChild(i,Left)) Left=i ;
    }
    forr(i,1,n+1)
    cout<<ans[i]<<" " ;
    cout<<"\n" ;
    forr(i,1,n) child[i]=0 ;
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
#ifndef ONLINE_JUDGE
    freopen(HUNGTT".inp", "r", stdin);
    freopen(HUNGTT".out", "w", stdout);
#endif  //ONLINE_JUDGE

    int numTest ;
    cin>>numTest ;
    while(numTest--)
    {
        read() ;
        solve() ;
    }

    return 0;
}
//-----------CODE MY DREAM------------

### Prompt

Please formulate 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
//--------------TTH-----------------
#include <bits/stdc++.h>
#define  HUNGTT "MEX Tree"
#define memset(f,a) memset(f,(a),sizeof(f))
#define forr(i,a,b) for(int i=(a);i<=(b);++i)
#define ford(i,a,b) for(int i=(a);i>=(b);--i)
#define fore(it,a) for(__typeof((a).begin()) it=(a).begin();it!=(a).end();++it)
#define F first
#define S second
#define mp make_pair
#define ALL(a) (a).begin(),(a).end()
#define MASK(i) (1LL<<(i))
#define BIT(x,i) (((x)>>(i))&1)

using namespace std;
mt19937 Rand(time(0));

typedef long long ll ;
typedef long double ld ;
typedef pair<int,int> ii ;

const int MAXN=2e5 ;


int in[MAXN+5],out[MAXN+5] ;
vector<int> adj[MAXN+5] ;
int n,times ;
const int LOG=18 ;
ll ans[MAXN+5] ;
int p[MAXN+5][LOG+2] ;
int bit[MAXN+5],child[MAXN+5] ;
int dep[MAXN+5] ;

void read()
{
    cin>>n ;
    forr(i,1,n)
    {
        adj[i].clear() ;
        in[i]=out[i]=bit[i]=dep[i]=0 ;
        child[i]=0 ;
        forr(x,0,LOG) p[i][x]=0 ;
    }
    forr(i,1,n+1) ans[i]=0 ;
    times=0 ;
    forr(LOVE,1,n-1)
    {
        int u,v ;
        cin>>u >>v ;
        ++u,++v ;
        adj[u].push_back(v) ;
        adj[v].push_back(u) ;
    }

}

void dfs(int u,int par=-1)
{
    in[u]=++times ;
    child[u]=1 ;
    forr(x,1,LOG) p[u][x]=p[p[u][x-1]][x-1] ;
    for(auto v: adj[u])
    {
        if(v==par) continue ;
        p[v][0]=u ;
        dep[v]=dep[u]+1 ;
        dfs(v,u) ;
        child[u]+=child[v] ;
    }
    out[u]=times ;
}

int Jump(int u,int x)
{
    forr(i,0,LOG)
    if(BIT(x,i)) u=p[u][i] ;
    return u ;
}

int LCA(int u,int v)
{
          if(dep[u]<dep[v]) swap(u,v) ;
          u=Jump(u,dep[u]-dep[v]) ;
          if(u==v) return u ;
          ford(x,LOG,0)
          if(p[u][x]!=p[v][x])
                    u=p[u][x],v=p[v][x] ;
          return p[u][0] ;
}

bool isChild(int u,int p)
{
    return in[u]>=in[p] && in[u]<=out[p] ;
}

int get(int x)
{
    int res=0 ;
    for(; x>0; x-=x& -x)
        res+=bit[x] ;
    return res ;
}
void update(int x,int val)
{
    for(; x<=n; x+=x& -x)
        bit[x]+=val ;
}

void solve()
{
    dfs(1) ;
    int Left=1,Right=1 ;
    update(1,1) ;
    int sum=1 ;
    for(auto u : adj[1])
    {
              ans[1]+=1LL*child[u]*(child[u]-1)/2;
              if(isChild(2,u)) ans[2]+=1LL*(child[u]-child[2])*sum ;
              else ans[2]+=1LL*(child[u])*sum ;
              if(isChild(2,u)) sum+=child[u]-child[2];
              else sum+=child[u] ;
    }
    forr(i,2,n+1)
    {
        if(in[Left]>in[Right]) swap(Left,Right) ;
        //cout<<i<<" "<<Left<<" "<<Right<<"\n" ;
        if(get(in[Left])+get(in[Right])-1!=i-1 || LCA(Left,Right)!=1)
        {
                 // if(n==2e5) cout<<"*"<<i<<"\n" ;
                  break ;
        }
        if(i<=n)
        {
            update(in[i],1) ;
            update(out[i]+1,-1) ;
        }
        if(get(in[Left])+get(in[Right])-1==i) continue ;
        if(Left!=Right && !isChild(Left,i) && !isChild(Right,i))
        {
            if(isChild(Right,Left))
            {
                int q=Jump(Right,dep[Right]-1) ;
                if(isChild(i,Right))
                    ans[i]=1LL*(child[Right]-child[i])*(child[1]-child[q]) ;
                else
                {
                    if(isChild(i,q))
                        ans[i]=1LL*(child[Right])*(child[1]-child[q]) ;
                    else ans[i]=1LL*child[Right]*(child[1]-child[q]-child[i]) ;
                }
            }
            else
            {
                if(!isChild(i,Left) && !isChild(i,Right))
                {
                    ans[i]=1LL*child[Left]*child[Right] ;
                }
                else
                {
                    if(isChild(i,Left)) ans[i]=1LL*(child[Left]-child[i])*child[Right] ;
                    else ans[i]=1LL*(child[Left])*(child[Right]-child[i]) ;
                }
            }
        }
        if(isChild(Left,i) || isChild(Right,i)) continue ;
        if(isChild(i,Right)) Right=i ;
        else if(isChild(i,Left)) Left=i ;
    }
    forr(i,1,n+1)
    cout<<ans[i]<<" " ;
    cout<<"\n" ;
    forr(i,1,n) child[i]=0 ;
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
#ifndef ONLINE_JUDGE
    freopen(HUNGTT".inp", "r", stdin);
    freopen(HUNGTT".out", "w", stdout);
#endif  //ONLINE_JUDGE

    int numTest ;
    cin>>numTest ;
    while(numTest--)
    {
        read() ;
        solve() ;
    }

    return 0;
}
//-----------CODE MY DREAM------------

```