#include <bits/stdc++.h>

using namespace std;
#define N 300030
#define ll long long
#define rep(i, l, r) for(auto i=(l);i<=(r);++i)
#define per(i, r, l) for(auto i=(r);i>=(l);--i)
int n, cnt, last[N], m;
struct edge {
    int to, next;
} e[N << 1];

inline void add(int u, int v) {
    e[++cnt] = {v, last[u]}, last[u] = cnt;
    e[++cnt] = {u, last[v]}, last[v] = cnt;
}

struct seg {
    int t[N];

    inline void clear(int n) {
        rep(i, 0, n)t[i] = 0;
    }

    inline void add(int x, int v) {
        for (; x <= n; t[x] += v, x += x & -x);
    }

    inline int ask(int x) {
        int res = 0;
        for (; x; res += t[x], x -= x & -x);
        return res;
    }
} T;

struct cutTree {
    int rk[N], dep[N], sz[N], id[N], ot[N], now, top[N], son[N], fa[N];

    inline void clear(int n) {
        now = 0;
        rep(i, 0, n)rk[i] = dep[i] = sz[i] = id[i] = ot[i] = top[i] = son[i] = fa[i] = 0;
    }

    inline void dfs1(int x, int d) {
        sz[x] = 1, dep[x] = d;
        for (int i = last[x], y; i; i = e[i].next)
            if ((y = e[i].to) != fa[x]) {
                fa[y] = x, dfs1(y, d + 1), sz[x] += sz[y];
                if (sz[y] > sz[son[x]])son[x] = y;
            }
    }

    inline void dfs2(int x, int d) {
        top[rk[id[x] = ++now] = x] = d;
        if (son[x])dfs2(son[x], d);
        for (int i = last[x], y; i; i = e[i].next)if ((y = e[i].to) != fa[x] && y != son[x])dfs2(y, y);
        ot[x] = now;
    }

    inline int lca(int l, int r) {
        for (; top[l] != top[r]; dep[top[l]] < dep[top[r]] ? r = fa[top[r]] : l = fa[top[l]]);
        return dep[l] < dep[r] ? l : r;
    }

    inline int up(int x, int k) {
        if (k < 0)return -1;
        while (top[x] != 1)
            if (dep[x] - dep[top[x]] < k)k -= dep[x] - dep[top[x]] + 1, x = fa[top[x]];
            else return rk[id[x] - k];
        return rk[id[x] - k];
    }

    inline int ask(int l, int r) {
        int res = 0;
        while (top[l] != top[r]) {
            if (dep[top[l]] < dep[top[r]])swap(l, r);
            res += T.ask(id[l]) - T.ask(id[top[l]] - 1);
            l = fa[top[l]];
        }
        if (dep[l] > dep[r])swap(l, r);
        return res + T.ask(id[r]) - T.ask(id[l] - 1);
    }

    inline void add(int l, int r, int v) {
        while (top[l] != top[r]) {
            if (dep[top[l]] < dep[top[r]])swap(l, r);
            T.add(id[top[l]], v), T.add(id[l] + 1, -v);
            l = fa[top[l]];
        }
        if (dep[l] > dep[r])swap(l, r);
        T.add(id[l], v), T.add(id[r] + 1, -v);;
    }

    inline int dis(int l, int r) {
        return dep[l] + dep[r] - 2 * dep[lca(l, r)];
    }
} CT;

int a[N];
ll ans[N];

inline ll work(int l, int r) {
    if (CT.dep[l] > CT.dep[r])swap(l, r);
    if (CT.lca(l, r) != l) {
        T.add(1, -1);
        T.add(CT.id[l], 1), T.add(CT.ot[l] + 1, -1);
        T.add(CT.id[r], 1), T.add(CT.ot[r] + 1, -1);
        CT.add(CT.fa[l], CT.fa[r], 1);
        return 1ll * CT.sz[l] * CT.sz[r];
    } else {
        int o = CT.up(r, CT.dis(l, r) - 1);
        T.add(CT.id[o], -1), T.add(CT.ot[o] + 1, 1);
        T.add(CT.id[r], 1), T.add(CT.ot[r] + 1, -1);
        CT.add(o, CT.fa[r], 1);
        return 1ll * (n - CT.sz[o]) * CT.sz[r];
    }
}

inline void solve() {
    scanf("%d", &n);
    cnt = 0;
    rep(i, 0, n)last[i] = ans[i] = 0;
    CT.clear(n), T.clear(n);
    T.add(1, 1);
    rep(i, 1, n - 1) {
        int u, v;
        scanf("%d%d", &u, &v);
        ++u, ++v;
        add(u, v);
    }
    CT.dfs1(1, 0), CT.dfs2(1, 1);
    for (int i = last[1]; i; i = e[i].next) {
        ans[0] += 1ll * CT.sz[e[i].to] * (CT.sz[e[i].to] - 1) / 2;
        ans[1] += 1ll * CT.sz[e[i].to] * (n - 1 - CT.sz[e[i].to]);
    }
    ans[1] >>= 1;
    ans[1] += n - 1;
    int L = 1, R = 2;
    ans[2] = work(L, R);
    rep(i, 3, n) {
        if (T.ask(CT.id[i]) <= 0)break;
        int dl = CT.dis(i, L), dr = CT.dis(i, R);
        if (dl + dr == CT.dis(L, R))ans[i] = ans[i - 1];
        else {
            if (dl > dr)ans[i] = work(L, R = i);
            else ans[i] = work(R, L = i);
            //ans[i - 1] -= ans[i];
        }
    }
    ll sm = 0;
    per(i, n, 1)ans[i] -= sm, sm += ans[i];

    rep(i, 0, n)printf("%lld ", ans[i]);
    puts("");
}

int main() {
    int T = 1;
    scanf("%d", &T);
    while (T--)solve();
}
### Prompt

Develop a solution in CPP to the problem described below:

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 N 300030
#define ll long long
#define rep(i, l, r) for(auto i=(l);i<=(r);++i)
#define per(i, r, l) for(auto i=(r);i>=(l);--i)
int n, cnt, last[N], m;
struct edge {
    int to, next;
} e[N << 1];

inline void add(int u, int v) {
    e[++cnt] = {v, last[u]}, last[u] = cnt;
    e[++cnt] = {u, last[v]}, last[v] = cnt;
}

struct seg {
    int t[N];

    inline void clear(int n) {
        rep(i, 0, n)t[i] = 0;
    }

    inline void add(int x, int v) {
        for (; x <= n; t[x] += v, x += x & -x);
    }

    inline int ask(int x) {
        int res = 0;
        for (; x; res += t[x], x -= x & -x);
        return res;
    }
} T;

struct cutTree {
    int rk[N], dep[N], sz[N], id[N], ot[N], now, top[N], son[N], fa[N];

    inline void clear(int n) {
        now = 0;
        rep(i, 0, n)rk[i] = dep[i] = sz[i] = id[i] = ot[i] = top[i] = son[i] = fa[i] = 0;
    }

    inline void dfs1(int x, int d) {
        sz[x] = 1, dep[x] = d;
        for (int i = last[x], y; i; i = e[i].next)
            if ((y = e[i].to) != fa[x]) {
                fa[y] = x, dfs1(y, d + 1), sz[x] += sz[y];
                if (sz[y] > sz[son[x]])son[x] = y;
            }
    }

    inline void dfs2(int x, int d) {
        top[rk[id[x] = ++now] = x] = d;
        if (son[x])dfs2(son[x], d);
        for (int i = last[x], y; i; i = e[i].next)if ((y = e[i].to) != fa[x] && y != son[x])dfs2(y, y);
        ot[x] = now;
    }

    inline int lca(int l, int r) {
        for (; top[l] != top[r]; dep[top[l]] < dep[top[r]] ? r = fa[top[r]] : l = fa[top[l]]);
        return dep[l] < dep[r] ? l : r;
    }

    inline int up(int x, int k) {
        if (k < 0)return -1;
        while (top[x] != 1)
            if (dep[x] - dep[top[x]] < k)k -= dep[x] - dep[top[x]] + 1, x = fa[top[x]];
            else return rk[id[x] - k];
        return rk[id[x] - k];
    }

    inline int ask(int l, int r) {
        int res = 0;
        while (top[l] != top[r]) {
            if (dep[top[l]] < dep[top[r]])swap(l, r);
            res += T.ask(id[l]) - T.ask(id[top[l]] - 1);
            l = fa[top[l]];
        }
        if (dep[l] > dep[r])swap(l, r);
        return res + T.ask(id[r]) - T.ask(id[l] - 1);
    }

    inline void add(int l, int r, int v) {
        while (top[l] != top[r]) {
            if (dep[top[l]] < dep[top[r]])swap(l, r);
            T.add(id[top[l]], v), T.add(id[l] + 1, -v);
            l = fa[top[l]];
        }
        if (dep[l] > dep[r])swap(l, r);
        T.add(id[l], v), T.add(id[r] + 1, -v);;
    }

    inline int dis(int l, int r) {
        return dep[l] + dep[r] - 2 * dep[lca(l, r)];
    }
} CT;

int a[N];
ll ans[N];

inline ll work(int l, int r) {
    if (CT.dep[l] > CT.dep[r])swap(l, r);
    if (CT.lca(l, r) != l) {
        T.add(1, -1);
        T.add(CT.id[l], 1), T.add(CT.ot[l] + 1, -1);
        T.add(CT.id[r], 1), T.add(CT.ot[r] + 1, -1);
        CT.add(CT.fa[l], CT.fa[r], 1);
        return 1ll * CT.sz[l] * CT.sz[r];
    } else {
        int o = CT.up(r, CT.dis(l, r) - 1);
        T.add(CT.id[o], -1), T.add(CT.ot[o] + 1, 1);
        T.add(CT.id[r], 1), T.add(CT.ot[r] + 1, -1);
        CT.add(o, CT.fa[r], 1);
        return 1ll * (n - CT.sz[o]) * CT.sz[r];
    }
}

inline void solve() {
    scanf("%d", &n);
    cnt = 0;
    rep(i, 0, n)last[i] = ans[i] = 0;
    CT.clear(n), T.clear(n);
    T.add(1, 1);
    rep(i, 1, n - 1) {
        int u, v;
        scanf("%d%d", &u, &v);
        ++u, ++v;
        add(u, v);
    }
    CT.dfs1(1, 0), CT.dfs2(1, 1);
    for (int i = last[1]; i; i = e[i].next) {
        ans[0] += 1ll * CT.sz[e[i].to] * (CT.sz[e[i].to] - 1) / 2;
        ans[1] += 1ll * CT.sz[e[i].to] * (n - 1 - CT.sz[e[i].to]);
    }
    ans[1] >>= 1;
    ans[1] += n - 1;
    int L = 1, R = 2;
    ans[2] = work(L, R);
    rep(i, 3, n) {
        if (T.ask(CT.id[i]) <= 0)break;
        int dl = CT.dis(i, L), dr = CT.dis(i, R);
        if (dl + dr == CT.dis(L, R))ans[i] = ans[i - 1];
        else {
            if (dl > dr)ans[i] = work(L, R = i);
            else ans[i] = work(R, L = i);
            //ans[i - 1] -= ans[i];
        }
    }
    ll sm = 0;
    per(i, n, 1)ans[i] -= sm, sm += ans[i];

    rep(i, 0, n)printf("%lld ", ans[i]);
    puts("");
}

int main() {
    int T = 1;
    scanf("%d", &T);
    while (T--)solve();
}
```