#include <bits/stdc++.h>
#define f first
#define s second
#define mp make_pair
#define pb push_back
#define p push
#define ins insert
#define t top
#define H 200100
#define INF 5000000000000000

using namespace std;
typedef pair<int,int> pii;
typedef long long int LL;

int T,n; LL N;
vector<int> adj[H];
int P[H];
LL C[H];
int L,R;
bool V[H];
LL ret[H];

void dfs(int v) {
    if (!V[v]) {
        V[v]=true;
        LL ret = 1;
        for (int u : adj[v]) {
            if (!V[u]) {
                P[u]=v;
                dfs(u);
                ret+=C[u];
            }
        }
        C[v]=ret;
    }
}
int tip;
bool good(int v) {
    if (V[v]) {
        int u=v;
        int prev;
        while (V[u]) {
            V[u]=false;
            prev=u;
            u=P[u];
        }
        if ((u==1) && (L==1) && (R==1)) {
            tip = prev;
            L=v;
            return true;
        }
        if (u==L) {
            L=v;
            return true;
        }
        if (u==R) {
            R=v;
            return true;
        }
        return false;
    } else {
        return true;
    }
}

LL CC(int v) {
    if (v==1) return C[1]-C[tip];
    else return C[v];
}

int main() {
    scanf("%d",&T);
    while (T--) {
        L=1;R=1;
        scanf("%d",&n);
        N = (LL)n;
        for (int i = 0; i <= N+1; i++) {
            adj[i].clear();
            V[i]=false;
            C[i]=0;
            P[i]=0;
            ret[i]=0;
        }

        for (int i = 0; i < N-1; i++) {
            int x,y; scanf("%d%d",&x,&y);
            x++; y++;
            adj[x].pb(y);
            adj[y].pb(x);
        }

        dfs(1);
        ret[0]=N*(N-1)/2;
        ret[1]=ret[0];
        for (int u : adj[1]) {
            ret[1]-=(C[u]-1)*C[u]/2;
        }
        V[1]=false;

        int vv;
        for (vv=2;vv<=N;vv++) {
            bool x = good(vv);
            //cout << "good? " << vv << x << endl;
            if (!x) {
                break;
            } else {
                ret[vv]=CC(L)*CC(R);
            }
        }
        for (;vv<=N+1;vv++) {
            ret[vv]=0;
        }

        // return the answers
        for (int i = 0; i < N+1; i++) {
            cout << ret[i]-ret[i+1] << " ";
            //cout << ret[i] << " ";
        }
        cout << endl;

    }
}

### Prompt

Please create a solution in cpp 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>
#define f first
#define s second
#define mp make_pair
#define pb push_back
#define p push
#define ins insert
#define t top
#define H 200100
#define INF 5000000000000000

using namespace std;
typedef pair<int,int> pii;
typedef long long int LL;

int T,n; LL N;
vector<int> adj[H];
int P[H];
LL C[H];
int L,R;
bool V[H];
LL ret[H];

void dfs(int v) {
    if (!V[v]) {
        V[v]=true;
        LL ret = 1;
        for (int u : adj[v]) {
            if (!V[u]) {
                P[u]=v;
                dfs(u);
                ret+=C[u];
            }
        }
        C[v]=ret;
    }
}
int tip;
bool good(int v) {
    if (V[v]) {
        int u=v;
        int prev;
        while (V[u]) {
            V[u]=false;
            prev=u;
            u=P[u];
        }
        if ((u==1) && (L==1) && (R==1)) {
            tip = prev;
            L=v;
            return true;
        }
        if (u==L) {
            L=v;
            return true;
        }
        if (u==R) {
            R=v;
            return true;
        }
        return false;
    } else {
        return true;
    }
}

LL CC(int v) {
    if (v==1) return C[1]-C[tip];
    else return C[v];
}

int main() {
    scanf("%d",&T);
    while (T--) {
        L=1;R=1;
        scanf("%d",&n);
        N = (LL)n;
        for (int i = 0; i <= N+1; i++) {
            adj[i].clear();
            V[i]=false;
            C[i]=0;
            P[i]=0;
            ret[i]=0;
        }

        for (int i = 0; i < N-1; i++) {
            int x,y; scanf("%d%d",&x,&y);
            x++; y++;
            adj[x].pb(y);
            adj[y].pb(x);
        }

        dfs(1);
        ret[0]=N*(N-1)/2;
        ret[1]=ret[0];
        for (int u : adj[1]) {
            ret[1]-=(C[u]-1)*C[u]/2;
        }
        V[1]=false;

        int vv;
        for (vv=2;vv<=N;vv++) {
            bool x = good(vv);
            //cout << "good? " << vv << x << endl;
            if (!x) {
                break;
            } else {
                ret[vv]=CC(L)*CC(R);
            }
        }
        for (;vv<=N+1;vv++) {
            ret[vv]=0;
        }

        // return the answers
        for (int i = 0; i < N+1; i++) {
            cout << ret[i]-ret[i+1] << " ";
            //cout << ret[i] << " ";
        }
        cout << endl;

    }
}

```