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. 

Solution (in CPP):

Solution:
#include<bits/stdc++.h>
#define fort(i,a,b) for(long long i=a;i<=b;i++)
#define forn(i,a,b) for(long long i=a;i>=b;i--)
#define rep(i,a,b) for(long long i=a;i<b;i++)
#define x first
#define y second
#define pb push_back
#define MP make_pair
using namespace std;
const long long  N=2e5+5;
long long  s1,s2,d,c,test,n,l[N][20],f[N],kq[N],h[N],cnt[N],kt[N],timer,tin[N],tout[N];
vector<long long > a[N];
void dfs(long long  u,long long  pa)
{
    tin[u]=++timer;
    h[u]=h[pa]+1;
    l[u][0]=pa;
    cnt[u]++;
    for(long long  v:a[u])
        if (v!=pa)
    {
        dfs(v,u);
        f[u]+=cnt[u]*cnt[v];
        cnt[u]+=cnt[v];
    }
    f[u]+=(n-cnt[u])*cnt[u];
    tout[u]=++timer;
}
void build_lca()
{
    fort(i,1,log2(n))
     fort(j,1,n)
      l[j][i]=l[l[j][i-1]][i-1];
}
long long  lca(long long  u,long long  v)
{
    if (h[u]<h[v]) swap(u,v);
    forn(i,log2(h[u]),0)
     if (h[l[u][i]]>=h[v]) u=l[u][i];
    if (u==v) return u;
    forn(i,log2(h[u]),0)
     if (l[u][i]!=l[v][i])
     {
         u=l[u][i];
         v=l[v][i];
     }
    return l[u][0];
}
void chinh(long long  x)
{
    if (kt[x]) return;
    kt[x]=1;
    chinh(l[x][0]);
}
bool con(long v,long u)
{
    return tin[u]<tin[v]&&tout[v]<tout[u];
}
int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>test;
    while (test--)
    {
        cin>>n;
        fort(i,1,n-1)
        {
            long long  u,v;
            cin>>u>>v;
            u++;v++;
            a[u].pb(v);
            a[v].pb(u);
        }
        dfs(1,0);
        build_lca();
        kq[1]=n*(n-1)/2-f[1];
        kq[n+1]=1;
        fort(i,1,n)
         if (a[i].size()>2) kq[n+1]=0;
        d=1;c=1;s1=0;s2=0;
        kt[1]=1;
        fort(i,2,n)
         if (!kt[i])
         {
             if (d!=c)
             {
                if (c==1)
                {
                    if (lca(i,d)!=1&&lca(i,d)!=d&&kt[lca(i,d)])
                    {
                        kq[i]=s2*cnt[d];
                        break;
                    }
                } else
                {
                    if (lca(i,d)!=d&&lca(i,c)!=c)
                    {
                        kq[i]=cnt[d]*cnt[c];
                        break;
                    }
                }
                if (con(i,d))
                    {

                        chinh(i);
                        s1=cnt[d]-cnt[i];
                        kq[i]=s1*s2;
                        d=i;
                        s1=cnt[d];
                    } else
                if (con(i,c))
                    {
                        chinh(i);
                        if (c==1) s2-=cnt[i];else
                            s2=cnt[c]-cnt[i];
                        kq[i]=s1*s2;
                        c=i;
                        s2=cnt[c];
                    }
            } else
            {
                chinh(i);
                for(long long  v:a[1])
                    if (!kt[v]) s2+=cnt[v];
                s2++;s1=cnt[i];
                kq[i]=f[1]-cnt[i]*s2;
                d=i;
            }
        }
        fort(i,1,n+1) cout<<kq[i]<<' ';cout<<'\n';
        fort(i,1,n) a[i].clear();
        fort(i,1,n+1) kq[i]=0;
        fort(i,1,n) cnt[i]=0;
        fort(i,1,n)
         fort(j,0,log2(n)) l[i][j]=0;
        fort(i,1,n) kt[i]=0;
        fort(i,1,n) f[i]=0;
        timer=0;
    }
}