#include <bits/stdc++.h>

using namespace std;

# define Rep(i,a,b) for(int i=a;i<=b;i++)
# define _Rep(i,a,b) for(int i=a;i>=b;i--)
# define RepG(i,u) for(int i=head[u];~i;i=e[i].next)

typedef long long ll;

const int N=2e5+5;

template<typename T> void read(T &x){
    x=0;int f=1;
    char c=getchar();
    for(;!isdigit(c);c=getchar())if(c=='-')f=-1;
    for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+c-'0';
    x*=f;
}

int t,n;
int head[N],cnt;
int st[N][20],dep[N];
int siz[N];
ll ans[N];
bool yestwo[N];

struct Edge{
    int to,next;
}e[N<<1];

void add(int x,int y){
    e[++cnt]=(Edge){y,head[x]},head[x]=cnt;
}

void dfs(int u,int fa){
    dep[u]=dep[fa]+1;
    st[u][0]=fa,siz[u]=1;
    Rep(i,1,19)st[u][i]=st[st[u][i-1]][i-1];
    if(u==2)yestwo[u]=true;
    RepG(i,u){
        int v=e[i].to;
        if(v==fa)continue;
        dfs(v,u);
        siz[u]+=siz[v];
        yestwo[u]|=yestwo[v];
    }
}

int lca(int x,int y){
    if(dep[x]<dep[y])swap(x,y);
    _Rep(i,19,0)if(dep[st[x][i]]>=dep[y])x=st[x][i];
    if(x==y)return x;
    _Rep(i,19,0)if(st[x][i]!=st[y][i])x=st[x][i],y=st[y][i];
    return st[x][0];
}

bool on(int p,int x,int y){
    int LCA=lca(x,y);
    if(lca(x,p)==LCA&&lca(y,p)==p)return true;
    if(lca(x,p)==p&&lca(y,p)==LCA)return true;
    return false;
}

int main()
{
    # ifdef hibike
    freopen("testdata.in","r",stdin);
    freopen("test1.out","w",stdout);
    # endif
    read(t);
    while(t--){
        read(n);
        Rep(i,1,n)head[i]=-1;cnt=0;
        Rep(i,1,n)Rep(j,0,19)st[i][j]=0;
        Rep(i,1,n)dep[i]=0;
        Rep(i,0,n)ans[i]=0,yestwo[i]=false;
        Rep(i,1,n-1){
            int x,y;
            read(x),read(y),x++,y++;
            add(x,y),add(y,x);
        }
        dfs(1,0);
        RepG(i,1){
            int v=e[i].to;
            ans[0]+=1ll*siz[v]*(siz[v]-1)/2;
        }
        ans[1]+=1ll*(n-siz[2])*(n-siz[2]-1)/2;
        RepG(i,1){
            int v=e[i].to;
            if(yestwo[v])ans[1]-=1ll*(siz[v]-siz[2])*(siz[v]-siz[2]-1)/2;
            else ans[1]-=1ll*siz[v]*(siz[v]-1)/2;
        } 
        int X=1,Y=2;
        Rep(i,2,n-1){
            if(X==-1&&Y==-1)break;
            if(dep[X]>dep[Y])swap(X,Y);
            int LCA=lca(X,Y);
            if(on(i+1,X,Y)){ans[i]=0;continue;}
            if(LCA==X){
                int v=Y;
                _Rep(j,19,0)if(dep[st[v][j]]>dep[X])v=st[v][j];
                if(lca(i+1,Y)==Y)ans[i]+=1ll*(siz[Y]-siz[i+1])*(n-siz[v]),Y=i+1;
                // i+1 in sub(y)
                else if(lca(i+1,Y)==X)ans[i]+=1ll*siz[Y]*(n-siz[v]-siz[i+1]),X=i+1;
                // i+1 in sub(x) but not in the subtree y is in
                else ans[i]+=1ll*siz[Y]*(n-siz[v]),X=-1,Y=-1;
                // i+1 in sub(x) but lca(i+1,y) is not x
            }
            else{
                if(lca(i+1,X)==X)ans[i]+=1ll*(siz[X]-siz[i+1])*siz[Y],X=i+1;
                // i+1 in sub(x)
                else if(lca(i+1,Y)==Y)ans[i]+=1ll*(siz[Y]-siz[i+1])*siz[X],Y=i+1;
                // i+1 in sub(y)
                else ans[i]+=1ll*siz[X]*siz[Y],X=-1,Y=-1;
                // i+1 in neither sub(x),sub(y)
            }
        }
        if(~X&&~Y)ans[n]=1;
        Rep(i,0,n)printf("%lld ",ans[i]);
        puts("");
    }
    return 0;
}
/*
1
5
1 0
2 0
3 2
4 3

*/
### 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 Rep(i,a,b) for(int i=a;i<=b;i++)
# define _Rep(i,a,b) for(int i=a;i>=b;i--)
# define RepG(i,u) for(int i=head[u];~i;i=e[i].next)

typedef long long ll;

const int N=2e5+5;

template<typename T> void read(T &x){
    x=0;int f=1;
    char c=getchar();
    for(;!isdigit(c);c=getchar())if(c=='-')f=-1;
    for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+c-'0';
    x*=f;
}

int t,n;
int head[N],cnt;
int st[N][20],dep[N];
int siz[N];
ll ans[N];
bool yestwo[N];

struct Edge{
    int to,next;
}e[N<<1];

void add(int x,int y){
    e[++cnt]=(Edge){y,head[x]},head[x]=cnt;
}

void dfs(int u,int fa){
    dep[u]=dep[fa]+1;
    st[u][0]=fa,siz[u]=1;
    Rep(i,1,19)st[u][i]=st[st[u][i-1]][i-1];
    if(u==2)yestwo[u]=true;
    RepG(i,u){
        int v=e[i].to;
        if(v==fa)continue;
        dfs(v,u);
        siz[u]+=siz[v];
        yestwo[u]|=yestwo[v];
    }
}

int lca(int x,int y){
    if(dep[x]<dep[y])swap(x,y);
    _Rep(i,19,0)if(dep[st[x][i]]>=dep[y])x=st[x][i];
    if(x==y)return x;
    _Rep(i,19,0)if(st[x][i]!=st[y][i])x=st[x][i],y=st[y][i];
    return st[x][0];
}

bool on(int p,int x,int y){
    int LCA=lca(x,y);
    if(lca(x,p)==LCA&&lca(y,p)==p)return true;
    if(lca(x,p)==p&&lca(y,p)==LCA)return true;
    return false;
}

int main()
{
    # ifdef hibike
    freopen("testdata.in","r",stdin);
    freopen("test1.out","w",stdout);
    # endif
    read(t);
    while(t--){
        read(n);
        Rep(i,1,n)head[i]=-1;cnt=0;
        Rep(i,1,n)Rep(j,0,19)st[i][j]=0;
        Rep(i,1,n)dep[i]=0;
        Rep(i,0,n)ans[i]=0,yestwo[i]=false;
        Rep(i,1,n-1){
            int x,y;
            read(x),read(y),x++,y++;
            add(x,y),add(y,x);
        }
        dfs(1,0);
        RepG(i,1){
            int v=e[i].to;
            ans[0]+=1ll*siz[v]*(siz[v]-1)/2;
        }
        ans[1]+=1ll*(n-siz[2])*(n-siz[2]-1)/2;
        RepG(i,1){
            int v=e[i].to;
            if(yestwo[v])ans[1]-=1ll*(siz[v]-siz[2])*(siz[v]-siz[2]-1)/2;
            else ans[1]-=1ll*siz[v]*(siz[v]-1)/2;
        } 
        int X=1,Y=2;
        Rep(i,2,n-1){
            if(X==-1&&Y==-1)break;
            if(dep[X]>dep[Y])swap(X,Y);
            int LCA=lca(X,Y);
            if(on(i+1,X,Y)){ans[i]=0;continue;}
            if(LCA==X){
                int v=Y;
                _Rep(j,19,0)if(dep[st[v][j]]>dep[X])v=st[v][j];
                if(lca(i+1,Y)==Y)ans[i]+=1ll*(siz[Y]-siz[i+1])*(n-siz[v]),Y=i+1;
                // i+1 in sub(y)
                else if(lca(i+1,Y)==X)ans[i]+=1ll*siz[Y]*(n-siz[v]-siz[i+1]),X=i+1;
                // i+1 in sub(x) but not in the subtree y is in
                else ans[i]+=1ll*siz[Y]*(n-siz[v]),X=-1,Y=-1;
                // i+1 in sub(x) but lca(i+1,y) is not x
            }
            else{
                if(lca(i+1,X)==X)ans[i]+=1ll*(siz[X]-siz[i+1])*siz[Y],X=i+1;
                // i+1 in sub(x)
                else if(lca(i+1,Y)==Y)ans[i]+=1ll*(siz[Y]-siz[i+1])*siz[X],Y=i+1;
                // i+1 in sub(y)
                else ans[i]+=1ll*siz[X]*siz[Y],X=-1,Y=-1;
                // i+1 in neither sub(x),sub(y)
            }
        }
        if(~X&&~Y)ans[n]=1;
        Rep(i,0,n)printf("%lld ",ans[i]);
        puts("");
    }
    return 0;
}
/*
1
5
1 0
2 0
3 2
4 3

*/
```