#include<bits/stdc++.h>
#define int ll
#define sz(x) int((x).size())
#define all(x) (x).begin(),(x).end()
using namespace std;
using ll = long long;
using pi = pair<int,int>;
const int inf = 0x3f3f3f3f3f3f3f3f;
const int minf = 0xc0c0c0c0c0c0c0c0;

const int N = 200200;

vector<int> adj[N];
int in[N];
int out[N];
int lv[N];
int par[N];
int sub[N];

signed main() {
    ios::sync_with_stdio(0); cin.tie(0);

    int TC; cin>>TC;
    int n;
    for (int tc=1; tc<=TC; tc++) {
        cin>>n;
        for (int i=0; i<n; i++) {
            adj[i].clear();
        }
        for (int i=1; i<n; i++) {
            int a,b; cin>>a>>b;
            adj[a].push_back(b);
            adj[b].push_back(a);
        }

        int num = 0;
        par[0] = -1;
        lv[0] = 0;

        function<void(int)> dfs = [&](int cur) {
            sub[cur] = 1;
            in[cur] = ++num;
            for (auto nxt : adj[cur]) {
                if (nxt == par[cur]) continue;
                par[nxt] = cur;
                lv[nxt] = lv[cur] + 1;
                dfs(nxt);
                sub[cur] += sub[nxt];
            }
            out[cur] = ++num;
        };

        dfs(0);

        int res = 0;

        for (auto nxt : adj[0]) {
            res += sub[nxt] * (sub[nxt] - 1) / 2;
        }

        cout<<res<<' ';

        int x = 1, y = 0;
        while (lv[x] != 1) {
            x = par[x];
        }

        res = 0;

        int prv = 0;

        for (auto nxt : adj[0]) {
            int s = sub[nxt];
            if (nxt == x) s -= sub[1];
            res += prv * s + s;
            prv += s;
        }

        cout<<res<<' ';

        int left = 1, right = 0;
        bool zero = 0;

        // x is subtree of y ?
        auto is_sub = [&](int x, int y) {
            return in[y] <= in[x] && out[x] <= out[y];
        };

        for (int i=2; i<=n; i++) {

            if (zero) {
                cout<<0<<' ';
                continue;
            }

            if (i != n) {
                if (right == 0) {
                    int L = sub[left];
                    int R = sub[0] - sub[x];

                    if (is_sub(i, x)) {
                        if (is_sub(i, left)) L -= sub[i];
                        else if (is_sub(left, i)) L = 0;
                    }
                    else R -= sub[i];

                    cout<<L*R<<' ';
                }
                else {
                    int L = sub[left];
                    int R = sub[right];
                    if (is_sub(i, x)) {
                        if (is_sub(i, left)) L -= sub[i];
                        else if (is_sub(left, i)) L = 0;
                    }
                    else if (is_sub(i, y)) {
                        if (is_sub(i, right)) R -= sub[i];
                        else if (is_sub(right, i)) R = 0;
                    }

                    cout<<L*R<<' ';
                }
            }
            else {
                cout<<1<<' ';
            }



            if (i == n) continue;

            if (right == 0) {
                if (is_sub(i, x)) {
                    if (is_sub(left, i)) continue;
                    if (is_sub(i, left)) left = i;
                    else zero = 1;
                }
                else {
                    right = i;
                    int y = right;
                    while (lv[y] != 1) {
                        y = par[y];
                    }
                }
            }
            else {
                if (is_sub(left, i) || is_sub(right, i)) continue;
                if (is_sub(i, left)) left = i;
                else if (is_sub(i, right)) right = i;
                else zero = 1;
            }
        }

        cout<<'\n';
    }
    return 0;
}
### Prompt

Create a solution in cpp for 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 int ll
#define sz(x) int((x).size())
#define all(x) (x).begin(),(x).end()
using namespace std;
using ll = long long;
using pi = pair<int,int>;
const int inf = 0x3f3f3f3f3f3f3f3f;
const int minf = 0xc0c0c0c0c0c0c0c0;

const int N = 200200;

vector<int> adj[N];
int in[N];
int out[N];
int lv[N];
int par[N];
int sub[N];

signed main() {
    ios::sync_with_stdio(0); cin.tie(0);

    int TC; cin>>TC;
    int n;
    for (int tc=1; tc<=TC; tc++) {
        cin>>n;
        for (int i=0; i<n; i++) {
            adj[i].clear();
        }
        for (int i=1; i<n; i++) {
            int a,b; cin>>a>>b;
            adj[a].push_back(b);
            adj[b].push_back(a);
        }

        int num = 0;
        par[0] = -1;
        lv[0] = 0;

        function<void(int)> dfs = [&](int cur) {
            sub[cur] = 1;
            in[cur] = ++num;
            for (auto nxt : adj[cur]) {
                if (nxt == par[cur]) continue;
                par[nxt] = cur;
                lv[nxt] = lv[cur] + 1;
                dfs(nxt);
                sub[cur] += sub[nxt];
            }
            out[cur] = ++num;
        };

        dfs(0);

        int res = 0;

        for (auto nxt : adj[0]) {
            res += sub[nxt] * (sub[nxt] - 1) / 2;
        }

        cout<<res<<' ';

        int x = 1, y = 0;
        while (lv[x] != 1) {
            x = par[x];
        }

        res = 0;

        int prv = 0;

        for (auto nxt : adj[0]) {
            int s = sub[nxt];
            if (nxt == x) s -= sub[1];
            res += prv * s + s;
            prv += s;
        }

        cout<<res<<' ';

        int left = 1, right = 0;
        bool zero = 0;

        // x is subtree of y ?
        auto is_sub = [&](int x, int y) {
            return in[y] <= in[x] && out[x] <= out[y];
        };

        for (int i=2; i<=n; i++) {

            if (zero) {
                cout<<0<<' ';
                continue;
            }

            if (i != n) {
                if (right == 0) {
                    int L = sub[left];
                    int R = sub[0] - sub[x];

                    if (is_sub(i, x)) {
                        if (is_sub(i, left)) L -= sub[i];
                        else if (is_sub(left, i)) L = 0;
                    }
                    else R -= sub[i];

                    cout<<L*R<<' ';
                }
                else {
                    int L = sub[left];
                    int R = sub[right];
                    if (is_sub(i, x)) {
                        if (is_sub(i, left)) L -= sub[i];
                        else if (is_sub(left, i)) L = 0;
                    }
                    else if (is_sub(i, y)) {
                        if (is_sub(i, right)) R -= sub[i];
                        else if (is_sub(right, i)) R = 0;
                    }

                    cout<<L*R<<' ';
                }
            }
            else {
                cout<<1<<' ';
            }



            if (i == n) continue;

            if (right == 0) {
                if (is_sub(i, x)) {
                    if (is_sub(left, i)) continue;
                    if (is_sub(i, left)) left = i;
                    else zero = 1;
                }
                else {
                    right = i;
                    int y = right;
                    while (lv[y] != 1) {
                        y = par[y];
                    }
                }
            }
            else {
                if (is_sub(left, i) || is_sub(right, i)) continue;
                if (is_sub(i, left)) left = i;
                else if (is_sub(i, right)) right = i;
                else zero = 1;
            }
        }

        cout<<'\n';
    }
    return 0;
}
```