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

typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

#define fastio() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define test() int t;cin>>t;for(int test=1;test<=t;test++)
#define pb push_back
#define nl cout<<"\n"
#define F first
#define S second
#define all(x) x.begin(),x.end()

template<class C> void min_self( C &a, C b ){ a = min(a,b); }
template<class C> void max_self( C &a, C b ){ a = max(a,b); }

const ll MOD = 1000000007;
ll mod( ll n, ll m=MOD ){ n%=m;if(n<0)n+=m;return n; }

const int MAXN = 2e5+5;
const int LOGN = 21;
const ll INF = 1e14;
int dx[] = {1,0,-1,0};
int dy[] = {0,1,0,-1};

template<class T1, class T2> void add( T1 &x, T2 y, ll m = MOD )
{
    x += y;
    if( x >= m )
        x -= m;
}

template<class T1, class T2> void sub( T1 &x, T2 y, ll m = MOD )
{
    x -= y;
    if( x < 0 )
        x += m;
}

class Tree
{
public:
    int N, LG;
    vector<vector<int>>gr, lca;
    vector<int>depth, parent, sz;
    Tree( int n )
    {
        N = n+5;
        LG = log(N);
        gr.resize(N);
        lca.resize(N, vector<int>(LG+5,0));
        depth.resize(N,0);
        parent.resize(N,0);
        sz.resize(N,1);
    }
    int log( int n )
    {
        int cnt = 0;
        while( n )
        {
            cnt++;
            n /= 2;
        }
        return cnt;
    }
    void addEdge( int u, int v )
    {
        gr[u].pb(v);
        gr[v].pb(u);
    }
    void addEdges( vector<vector<int>>&edges )
    {
        for( auto edge : edges )
        {
            addEdge( edge[0], edge[1] );
        }
    }
    void dfs( int v, int p = -1 )
    {
        sz[v] = 1;
        if( p != -1 )
        {
            parent[v] = p;
            lca[v][0] = p;
            for(int j=1;j<=LG;j++)
                lca[v][j] = lca[ lca[v][j-1] ][j-1];
        }
        for( auto to : gr[v] )
        {
            if( to != p )
            {
                depth[to] = depth[v] + 1;
                dfs(to, v);
                sz[v] += sz[to];
            }
        }
    }
    int up( int u, int h )
    {
        if( h <= 0 ) return u;
        int cnt = 0;
        while( h )
        {
            if( h&1 )
                u = lca[u][cnt];
            cnt++;
            h >>= 1;
        }
        return u;
    }
    int find_lca( int u, int v )
    {
        u = up(u, depth[u]-depth[v]);
        v = up(v, depth[v]-depth[u]);
        for(int bit=LG;bit>=0;bit--)
        {
            if( lca[u][bit] != lca[v][bit] )
            {
                u = lca[u][bit];
                v = lca[v][bit];
            }
        }
        while( u != v )
        {
            u = lca[u][0];
            v = lca[v][0];
        }
        return u;
    }
    int distance( int u, int v )
    {
        int ancestor = find_lca(u,v);
        return depth[u] + depth[v] - 2*depth[ancestor];
    }
};



int main() 
{
    fastio();
    #ifndef ONLINE_JUDGE
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif


    test()
    {
        int n; cin>>n;
        Tree tree(n);

        for(int i=1; i<n; i++)
        {
            int u, v; cin>>u>>v;
            tree.addEdge(u,v);
        }

        tree.dfs(0);

        vector<ll> ans(n+1,0);

        ll total = 1;
        for(auto nxt: tree.gr[0])
        {
            ll sznow = tree.sz[nxt];
            ans[0] += (sznow * (sznow-1))/2;
            ll now = sznow;
            if(tree.find_lca(nxt,1) == nxt)
                now -= tree.sz[1];

            ans[1] += (total * now);
            total += now;
        }

        int end[2] = {0,1};
        for(auto nxt: tree.gr[0])
        {
            if(tree.find_lca(nxt, 1) == nxt)
            {
                tree.sz[0] -= tree.sz[nxt];
                break;
            }
        }

        for(int i=2; i<n; i++)
        {
            int replace;
            if(tree.find_lca(i,end[0]) == end[0] && tree.find_lca(i,end[1]) == 0)
                replace = 0;
            else if(tree.find_lca(i,end[1]) == end[1] && tree.find_lca(i,end[0]) == 0)
                replace = 1;
            else
            {
                if(tree.find_lca(i,end[0]) == i || tree.find_lca(i,end[1]) == i)
                {
                    ans[i] = 0;
                    continue;
                }
                else
                {
                    ans[i] = (ll)tree.sz[end[0]] * tree.sz[end[1]];
                    break;
                }
            }

            int now = end[replace];
            tree.sz[now] -= tree.sz[i];

            ans[i] = (ll)tree.sz[end[0]] * tree.sz[end[1]];
            // cout<<i<<" "<<tree.sz[end[0]]<<" "<<tree.sz[end[1]],nl;

            end[replace] = i;
        }

        ll sum = 0;
        ll mx = ((ll)n*(n-1))/2;
        for(int i=0; i<n; i++)
            sum += ans[i];

        ans[n] = mx - sum;

        for(int i=0; i<=n; i++)
            cout<<ans[i]<<" ";
        nl;
    }
    

    cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
    return 0;
}


### Prompt

Your challenge is to write 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;

typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

#define fastio() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define test() int t;cin>>t;for(int test=1;test<=t;test++)
#define pb push_back
#define nl cout<<"\n"
#define F first
#define S second
#define all(x) x.begin(),x.end()

template<class C> void min_self( C &a, C b ){ a = min(a,b); }
template<class C> void max_self( C &a, C b ){ a = max(a,b); }

const ll MOD = 1000000007;
ll mod( ll n, ll m=MOD ){ n%=m;if(n<0)n+=m;return n; }

const int MAXN = 2e5+5;
const int LOGN = 21;
const ll INF = 1e14;
int dx[] = {1,0,-1,0};
int dy[] = {0,1,0,-1};

template<class T1, class T2> void add( T1 &x, T2 y, ll m = MOD )
{
    x += y;
    if( x >= m )
        x -= m;
}

template<class T1, class T2> void sub( T1 &x, T2 y, ll m = MOD )
{
    x -= y;
    if( x < 0 )
        x += m;
}

class Tree
{
public:
    int N, LG;
    vector<vector<int>>gr, lca;
    vector<int>depth, parent, sz;
    Tree( int n )
    {
        N = n+5;
        LG = log(N);
        gr.resize(N);
        lca.resize(N, vector<int>(LG+5,0));
        depth.resize(N,0);
        parent.resize(N,0);
        sz.resize(N,1);
    }
    int log( int n )
    {
        int cnt = 0;
        while( n )
        {
            cnt++;
            n /= 2;
        }
        return cnt;
    }
    void addEdge( int u, int v )
    {
        gr[u].pb(v);
        gr[v].pb(u);
    }
    void addEdges( vector<vector<int>>&edges )
    {
        for( auto edge : edges )
        {
            addEdge( edge[0], edge[1] );
        }
    }
    void dfs( int v, int p = -1 )
    {
        sz[v] = 1;
        if( p != -1 )
        {
            parent[v] = p;
            lca[v][0] = p;
            for(int j=1;j<=LG;j++)
                lca[v][j] = lca[ lca[v][j-1] ][j-1];
        }
        for( auto to : gr[v] )
        {
            if( to != p )
            {
                depth[to] = depth[v] + 1;
                dfs(to, v);
                sz[v] += sz[to];
            }
        }
    }
    int up( int u, int h )
    {
        if( h <= 0 ) return u;
        int cnt = 0;
        while( h )
        {
            if( h&1 )
                u = lca[u][cnt];
            cnt++;
            h >>= 1;
        }
        return u;
    }
    int find_lca( int u, int v )
    {
        u = up(u, depth[u]-depth[v]);
        v = up(v, depth[v]-depth[u]);
        for(int bit=LG;bit>=0;bit--)
        {
            if( lca[u][bit] != lca[v][bit] )
            {
                u = lca[u][bit];
                v = lca[v][bit];
            }
        }
        while( u != v )
        {
            u = lca[u][0];
            v = lca[v][0];
        }
        return u;
    }
    int distance( int u, int v )
    {
        int ancestor = find_lca(u,v);
        return depth[u] + depth[v] - 2*depth[ancestor];
    }
};



int main() 
{
    fastio();
    #ifndef ONLINE_JUDGE
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif


    test()
    {
        int n; cin>>n;
        Tree tree(n);

        for(int i=1; i<n; i++)
        {
            int u, v; cin>>u>>v;
            tree.addEdge(u,v);
        }

        tree.dfs(0);

        vector<ll> ans(n+1,0);

        ll total = 1;
        for(auto nxt: tree.gr[0])
        {
            ll sznow = tree.sz[nxt];
            ans[0] += (sznow * (sznow-1))/2;
            ll now = sznow;
            if(tree.find_lca(nxt,1) == nxt)
                now -= tree.sz[1];

            ans[1] += (total * now);
            total += now;
        }

        int end[2] = {0,1};
        for(auto nxt: tree.gr[0])
        {
            if(tree.find_lca(nxt, 1) == nxt)
            {
                tree.sz[0] -= tree.sz[nxt];
                break;
            }
        }

        for(int i=2; i<n; i++)
        {
            int replace;
            if(tree.find_lca(i,end[0]) == end[0] && tree.find_lca(i,end[1]) == 0)
                replace = 0;
            else if(tree.find_lca(i,end[1]) == end[1] && tree.find_lca(i,end[0]) == 0)
                replace = 1;
            else
            {
                if(tree.find_lca(i,end[0]) == i || tree.find_lca(i,end[1]) == i)
                {
                    ans[i] = 0;
                    continue;
                }
                else
                {
                    ans[i] = (ll)tree.sz[end[0]] * tree.sz[end[1]];
                    break;
                }
            }

            int now = end[replace];
            tree.sz[now] -= tree.sz[i];

            ans[i] = (ll)tree.sz[end[0]] * tree.sz[end[1]];
            // cout<<i<<" "<<tree.sz[end[0]]<<" "<<tree.sz[end[1]],nl;

            end[replace] = i;
        }

        ll sum = 0;
        ll mx = ((ll)n*(n-1))/2;
        for(int i=0; i<n; i++)
            sum += ans[i];

        ans[n] = mx - sum;

        for(int i=0; i<=n; i++)
            cout<<ans[i]<<" ";
        nl;
    }
    

    cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
    return 0;
}


```