// i'm wutan
#include <bits/stdc++.h>
#define EL cout<<endl
#define pli pair<ll,int>
#define pll pair<ll,ll>
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define sz(a) int(a.size())
#define FU(x,a,b) for(int x=int(a);x<=int(b);x++)
#define FD(x,a,b) for(int x=int(a);x>=int(b);x--)
#define PROB "1527D"

using namespace std;
/*
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

// ordered_set name_of_set;
// int pos = *name_of_set.find_by_order(int(value));
*/
typedef long long ll;
typedef double db;

/*
template <typename T>
inline void read(T& x){
    bool Neg = false;
    char c;
    for (c = getchar(); c < '0' | c > '9'; c = getchar())
        if (c == '-') Neg = !Neg;
    x = c - '0';
    for (c = getchar(); c >= '0' && c <= '9'; c = getchar())
        x = x * 10 + c - '0';
    if (Neg) x = -x;
}

template <typename T>
inline void write(T x)
{
    if (x < 0)
    {
        putchar('-'); x = -x;
    }
    T p = 1;
    for (T temp = x / 10; temp > 0; temp /= 10) p *= 10;
    for (; p > 0; x %= p, p /= 10) putchar(x / p + '0');
}
*/

void setIO() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    if(fopen(PROB".inp", "r")){
        freopen(PROB".inp", "r",stdin);
        freopen(PROB".out", "w",stdout);
    }
}

const int N = 2e5 + 2;
int n, par[N][19], chi[N], h[N];
ll res[N];
vector < vector < int > > a;

void readinp(){
    cin >> n;
    a.resize(n + 1);
    FU(i, 2, n){
        int u, v;
        cin >> u >> v;
        a[u].pb(v);
        a[v].pb(u);
    }
}

void dfs (int u, int p){
    chi[u] = 1;
    for (auto v : a[u]) if (v != p){
        h[v] = h[u] + 1;
        par[v][0] = u;
        dfs(v, u);
        chi[u]+= chi[v];
    }
}

int lca(int u, int v){
    if (h[u] < h[v]) swap(u, v);
    FD(k, 18, 0) if (h[par[u][k]] >= h[v]) u = par[u][k];
    FD(k, 18, 0) if (par[u][k] != par[v][k]) u = par[u][k], v = par[v][k];
    return (u == v ? u : par[u][0]);
}

int dis(int u, int v){
    return h[u] + h[v] - 2 * h[lca(u, v)];
}

int jump(int u, int l){
    FD(k, 18, 0){
        if (l >= (1 << k)){
            u = par[u][k];
            l-= (1 << k);
        }
    }
    return u;
}

void solve(){
    par[0][0] = 0;
    h[0] = 0;
    dfs(0, 0);
    FU(k, 1, 18) FU(u, 1, n)
        par[u][k] = par[par[u][k-1]][k-1];


    int X = 0, Y = 0;
    for (auto v : a[0]){
        ll s = ll(chi[v]);
        res[0]+= s * (s - 1) / 2LL;
    }
    bool OK = true;
    FU(i, 1, n - 1){
        int anc1 = lca(X, i);
        int anc2 = lca(Y, i);
        int anc3 = lca(X, Y);

        if (dis(X, i) + dis(i, Y) == dis(X, Y)){
            continue;
        }
        if (dis(X, Y) + dis(Y, i) == dis(X, i)
         || dis(X, Y) + dis(X, i) == dis(Y, i))
            ;
        else {
            ll sumX = chi[X] - (anc3 == X) * chi[jump(Y, h[Y] - h[X] - 1)];
            ll sumY = chi[Y];
            res[i] = sumX * sumY;
            OK = false;
            break;
        }


        if (X == Y){
            assert(X == 0);
            assert(i == 1);
            vector < int > arr;
            ll sum = 0;
            for (auto v : a[X]){
                ll t = chi[v] - chi[1] * (lca(v, 1) == v);
                arr.pb(t);
                sum+= t;
            }
            sum+= 1; arr.pb(1);
            for (ll t : arr){
                sum-= t;
                res[1]+= t * sum;
            }
            Y = i;
            continue;
        }

        if (anc1 == X && anc2 == Y){
            assert(anc3 == X);
            ll sumX = chi[X] - chi[jump(Y, h[Y] - h[X] - 1)];
            ll sumY = chi[Y] - chi[i];
            res[i] = sumX * sumY;
            Y = i;
        }
        else{
            if (anc1 == X){
                assert(anc2 != Y);
                ll sumX = chi[X] - chi[i]
                - (anc3 == X) * chi[jump(Y, h[Y] - h[X] - 1)];
                ll sumY = chi[Y];
                res[i] = sumX * sumY;
                X = i;
            }
            else{
                assert(anc1 != X);
                ll sumX = chi[X] - (anc3 == X) * chi[jump(Y, h[Y] - h[X] - 1)];
                ll sumY = chi[Y] - chi[i];
                res[i] = sumX * sumY;
                Y = i;
            }
        }

        if (lca(X, Y) == Y) swap(X, Y);
    }
//    EL;EL;
//    FU(x, 0, n){
//        int cnt = 0;
//        FU(u, 0, n - 1) FU(v, u + 1, n - 1){
//            bool ok = (dis(u, x) + dis(x, v) != dis(u, v));
//            FU(y, 0, x - 1) {
//                if (dis(u, y) + dis(y, v) == dis(u, v))
//                    ;
//                else ok = false;
//            }
////            if (ok) cout << u << ' ' << v ,EL;
//            cnt+= ok;
//        }
//        cout << cnt << ' ' ;
//    }
    if (n == 2){
        cout << 0 << ' ' << 0 << ' ' << 1; EL;

    }
    else{
        FU(x, 0, n){
            if (x != n) cout << res[x] << ' ';
            else cout << OK;
        }
        EL;
    }
    FU(u, 0, n) {
        h[u] = chi[u] = res[u] = 0;
        FU(k, 0, 18) par[u][k] = 0;
    }
    a.clear();
}

int main(){
    setIO();
    int t = 1;
    cin >> t;
    while (t--){
        readinp();
        solve();
    }
}

### Prompt

In CPP, your task is to solve 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
// i'm wutan
#include <bits/stdc++.h>
#define EL cout<<endl
#define pli pair<ll,int>
#define pll pair<ll,ll>
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define sz(a) int(a.size())
#define FU(x,a,b) for(int x=int(a);x<=int(b);x++)
#define FD(x,a,b) for(int x=int(a);x>=int(b);x--)
#define PROB "1527D"

using namespace std;
/*
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

// ordered_set name_of_set;
// int pos = *name_of_set.find_by_order(int(value));
*/
typedef long long ll;
typedef double db;

/*
template <typename T>
inline void read(T& x){
    bool Neg = false;
    char c;
    for (c = getchar(); c < '0' | c > '9'; c = getchar())
        if (c == '-') Neg = !Neg;
    x = c - '0';
    for (c = getchar(); c >= '0' && c <= '9'; c = getchar())
        x = x * 10 + c - '0';
    if (Neg) x = -x;
}

template <typename T>
inline void write(T x)
{
    if (x < 0)
    {
        putchar('-'); x = -x;
    }
    T p = 1;
    for (T temp = x / 10; temp > 0; temp /= 10) p *= 10;
    for (; p > 0; x %= p, p /= 10) putchar(x / p + '0');
}
*/

void setIO() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    if(fopen(PROB".inp", "r")){
        freopen(PROB".inp", "r",stdin);
        freopen(PROB".out", "w",stdout);
    }
}

const int N = 2e5 + 2;
int n, par[N][19], chi[N], h[N];
ll res[N];
vector < vector < int > > a;

void readinp(){
    cin >> n;
    a.resize(n + 1);
    FU(i, 2, n){
        int u, v;
        cin >> u >> v;
        a[u].pb(v);
        a[v].pb(u);
    }
}

void dfs (int u, int p){
    chi[u] = 1;
    for (auto v : a[u]) if (v != p){
        h[v] = h[u] + 1;
        par[v][0] = u;
        dfs(v, u);
        chi[u]+= chi[v];
    }
}

int lca(int u, int v){
    if (h[u] < h[v]) swap(u, v);
    FD(k, 18, 0) if (h[par[u][k]] >= h[v]) u = par[u][k];
    FD(k, 18, 0) if (par[u][k] != par[v][k]) u = par[u][k], v = par[v][k];
    return (u == v ? u : par[u][0]);
}

int dis(int u, int v){
    return h[u] + h[v] - 2 * h[lca(u, v)];
}

int jump(int u, int l){
    FD(k, 18, 0){
        if (l >= (1 << k)){
            u = par[u][k];
            l-= (1 << k);
        }
    }
    return u;
}

void solve(){
    par[0][0] = 0;
    h[0] = 0;
    dfs(0, 0);
    FU(k, 1, 18) FU(u, 1, n)
        par[u][k] = par[par[u][k-1]][k-1];


    int X = 0, Y = 0;
    for (auto v : a[0]){
        ll s = ll(chi[v]);
        res[0]+= s * (s - 1) / 2LL;
    }
    bool OK = true;
    FU(i, 1, n - 1){
        int anc1 = lca(X, i);
        int anc2 = lca(Y, i);
        int anc3 = lca(X, Y);

        if (dis(X, i) + dis(i, Y) == dis(X, Y)){
            continue;
        }
        if (dis(X, Y) + dis(Y, i) == dis(X, i)
         || dis(X, Y) + dis(X, i) == dis(Y, i))
            ;
        else {
            ll sumX = chi[X] - (anc3 == X) * chi[jump(Y, h[Y] - h[X] - 1)];
            ll sumY = chi[Y];
            res[i] = sumX * sumY;
            OK = false;
            break;
        }


        if (X == Y){
            assert(X == 0);
            assert(i == 1);
            vector < int > arr;
            ll sum = 0;
            for (auto v : a[X]){
                ll t = chi[v] - chi[1] * (lca(v, 1) == v);
                arr.pb(t);
                sum+= t;
            }
            sum+= 1; arr.pb(1);
            for (ll t : arr){
                sum-= t;
                res[1]+= t * sum;
            }
            Y = i;
            continue;
        }

        if (anc1 == X && anc2 == Y){
            assert(anc3 == X);
            ll sumX = chi[X] - chi[jump(Y, h[Y] - h[X] - 1)];
            ll sumY = chi[Y] - chi[i];
            res[i] = sumX * sumY;
            Y = i;
        }
        else{
            if (anc1 == X){
                assert(anc2 != Y);
                ll sumX = chi[X] - chi[i]
                - (anc3 == X) * chi[jump(Y, h[Y] - h[X] - 1)];
                ll sumY = chi[Y];
                res[i] = sumX * sumY;
                X = i;
            }
            else{
                assert(anc1 != X);
                ll sumX = chi[X] - (anc3 == X) * chi[jump(Y, h[Y] - h[X] - 1)];
                ll sumY = chi[Y] - chi[i];
                res[i] = sumX * sumY;
                Y = i;
            }
        }

        if (lca(X, Y) == Y) swap(X, Y);
    }
//    EL;EL;
//    FU(x, 0, n){
//        int cnt = 0;
//        FU(u, 0, n - 1) FU(v, u + 1, n - 1){
//            bool ok = (dis(u, x) + dis(x, v) != dis(u, v));
//            FU(y, 0, x - 1) {
//                if (dis(u, y) + dis(y, v) == dis(u, v))
//                    ;
//                else ok = false;
//            }
////            if (ok) cout << u << ' ' << v ,EL;
//            cnt+= ok;
//        }
//        cout << cnt << ' ' ;
//    }
    if (n == 2){
        cout << 0 << ' ' << 0 << ' ' << 1; EL;

    }
    else{
        FU(x, 0, n){
            if (x != n) cout << res[x] << ' ';
            else cout << OK;
        }
        EL;
    }
    FU(u, 0, n) {
        h[u] = chi[u] = res[u] = 0;
        FU(k, 0, 18) par[u][k] = 0;
    }
    a.clear();
}

int main(){
    setIO();
    int t = 1;
    cin >> t;
    while (t--){
        readinp();
        solve();
    }
}

```