#include <iostream>
#include <iomanip>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <queue>
#include <deque>
#include <cmath>
#include <algorithm>
#include <cassert>
#include <chrono>
#include <random>
#include <string>
#include <numeric>
#include <complex>
#include <tuple>
#include <utility>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef string str;

#define pb push_back
#define ppp pop_back
#define pii pair<int, int>
#define pll pair<ll, ll>
#define fi first
#define se second
#define stie std::tie
#define vec vector
#define forn(i, l, r) for (int i=l; i<=r; i++)
#define forb(i, r, l) for (int i=r; i>=l; i--)
#define emp empty
#define beg begin
#define ins insert
#define cle clear
#define era erase
#define que queue
#define pque priority_queue
#define mset multiset
#define deq deque
#define sta stack
#define con const
#define rsz resize
#define ass assign
#define lowb lower_bound
#define uppb upper_bound

template <class T> void mini(T& a, T b) { a = min(a, b); }
template <class T> void maxi(T& a, T b) { a = max(a, b); }
template <class T> T gcd(T a, T b) { return b == 0 ? a : gcd(b, a % b); }
template <class T1, class T2>
ostream& operator<<(ostream& os, pair<T1, T2> const& a) { return os << "[" << a.first << ", " << a.second << "]"; }
template <class Ch, class Tr, class Container>
basic_ostream<Ch, Tr>& operator<<(basic_ostream<Ch, Tr>& os, Container const& a) { os << "{ "; for (auto& i : a) os << i << " "; return os << "}"; }
template <class T> void out(T a) { cout << a << endl; }
template <class T, class... Args> void out(T a, Args... args) { cout << a << " "; out(args...); }
template <class T> void out(std::initializer_list<T> a) { for (auto i : a) { cout << i << " "; } cout << endl; }
template <class T> void out(vector<vector<T>> a) { for (vector<T> i : a) out(i); }
template <class T> void out_(T a[], int l, int r) { for (int i = l; i <= r; i++) cout << a[i] << " "; cout << endl; }
void out() { cout << "OK" << endl; }
template <class T> void sort(vector<T>& a) { sort(a.begin(), a.end()); }
template <class T> void rever(vector<T>& a) { reverse(a.begin(), a.end()); }
template <class T> void uniq(vector<T>& a) { sort(a); a.erase(unique(a.begin(), a.end()), a.end()); }
template <class T> vector<T> set_int(vector<T> a, vector<T> b) { sort(a); sort(b); vector<T> res;
set_intersection(a.begin(), a.end(), b.begin(), b.end(), back_inserter(res)); return res; }
clock_t start_time; void start_timer() { start_time = clock(); }
double get_time() { return (double)(clock() - start_time) / CLOCKS_PER_SEC; }
#if __SIZEOF_INT128__ >= 16
typedef __int128 LL;
istream& operator>>(istream& in, __int128& a) { int64_t b; in >> b; a = b; return in; }
ostream& operator<<(ostream& out, const __int128 a) {
    unsigned __int128 b = a < 0 ? -a : a; char buf[128]; char* c = end(buf); do { --c; *c = "0123456789"[b % 10]; b /= 10; } while (b);
    if (a < 0) { --c; *c = '-'; } int64_t len = end(buf) - c; out.rdbuf()->sputn(c, len); return out;
}
#endif

// solve the problem or die trying
// do something, stay focused
// look for stupid bugs
// guess, slow, stress
// the solution is always simple

const int N = 2e5 + 10;
const int L = 21;

vector<int> g[N];
int tin[N];
int tout[N];
int up[N][L];
int timer = 1;
ll sz[N];
ll ans[N];
int to[N];
vec<int> all[N];

void init(int n) {
    forn(i, 0, n + 5) {
        g[i].cle();
        tin[i] = 0;
        tout[i] = 0;
        forn(j, 0, L - 1) {
            up[i][j] = 0;
        }
        sz[i] = 0;
        ans[i] = 0;
        to[i] = 0;
        all[i].cle();
    }
    timer = 1;
}

void dfs_lca(int v = 1, int p = 1) {
    tin[v] = timer++;
    up[v][0] = p;
    for (int i = 1; i < L; i++) {
        up[v][i] = up[up[v][i - 1]][i - 1];
    }
    sz[v] = 1;
    all[v].pb(v);
    for (int u : g[v]) {
        if (u != p) {
            dfs_lca(u, v);
            sz[v] += sz[u];
            if (v == 1) {
                to[1] = 1;
                for (int i : all[u]) {
                    to[i] = u;
                }
            }
            if (all[v].size() < all[u].size()) {
                swap(all[v], all[u]);
            }
            for (int i : all[u]) {
                all[v].pb(i);
            }
        }
    }
    tout[v] = timer - 1;
}

bool is_anc(int u, int v) {
    return tin[u] <= tin[v] && tin[v] <= tout[u];
}

int lca(int u, int v) {
    if (is_anc(u, v)) return u;
    if (is_anc(v, u)) return v;
    for (int i = L - 1; i >= 0; i--) {
        if (!is_anc(up[u][i], v)) u = up[u][i];
    }
    return up[u][0];
}

ll f(ll n) {
    return n * (n - 1) / 2;
}

void Solve() {
    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        init(n);
        forn(i, 1, n - 1) {
            int u, v;
            cin >> u >> v;
            u++;
            v++;
            g[u].pb(v);
            g[v].pb(u);
        }
        dfs_lca();
        to[1] = 1;
        ans[1] = f(n);
        ans[2] = f(n);
        for (int i : g[1]) {
            ans[2] -= f(sz[i]);
        }
        int l = 1;
        int r = 1;
        forn(i, 2, n) {
            int v = i;
            if (!is_anc(l, v) && !is_anc(v, l) && !is_anc(r, v) && !is_anc(v, r)) {
                break;
            }
            if (r == 1) swap(l, r);
            if (is_anc(r, v)) {
                r = v;
            }
            else if (is_anc(l, v) && !is_anc(v, r)) {
                l = v;
            }
            int L = to[l];
            int R = to[r];
            if (R == 1) {
                swap(l, r);
                swap(L, R);
            }
            if (lca(l, r) != 1) {
                break;
            }
            else if (L == 1) {
                ans[i + 1] = (sz[1] - sz[R]) * sz[r];
            }
            else {
                ans[i + 1] = sz[l] * sz[r];
            }
        }
        forn(i, 1, n + 1) {
            ans[i] -= ans[i + 1];
        }
        forn(i, 1, n + 1) {
            cout << ans[i] << " ";
        }
        cout << "\n";
    }
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
#ifdef LOCAL
    freopen("usr/share/man/man1/input.txt", "r", stdin);
#endif
    start_timer();
    Solve();
    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 <iostream>
#include <iomanip>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <queue>
#include <deque>
#include <cmath>
#include <algorithm>
#include <cassert>
#include <chrono>
#include <random>
#include <string>
#include <numeric>
#include <complex>
#include <tuple>
#include <utility>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef string str;

#define pb push_back
#define ppp pop_back
#define pii pair<int, int>
#define pll pair<ll, ll>
#define fi first
#define se second
#define stie std::tie
#define vec vector
#define forn(i, l, r) for (int i=l; i<=r; i++)
#define forb(i, r, l) for (int i=r; i>=l; i--)
#define emp empty
#define beg begin
#define ins insert
#define cle clear
#define era erase
#define que queue
#define pque priority_queue
#define mset multiset
#define deq deque
#define sta stack
#define con const
#define rsz resize
#define ass assign
#define lowb lower_bound
#define uppb upper_bound

template <class T> void mini(T& a, T b) { a = min(a, b); }
template <class T> void maxi(T& a, T b) { a = max(a, b); }
template <class T> T gcd(T a, T b) { return b == 0 ? a : gcd(b, a % b); }
template <class T1, class T2>
ostream& operator<<(ostream& os, pair<T1, T2> const& a) { return os << "[" << a.first << ", " << a.second << "]"; }
template <class Ch, class Tr, class Container>
basic_ostream<Ch, Tr>& operator<<(basic_ostream<Ch, Tr>& os, Container const& a) { os << "{ "; for (auto& i : a) os << i << " "; return os << "}"; }
template <class T> void out(T a) { cout << a << endl; }
template <class T, class... Args> void out(T a, Args... args) { cout << a << " "; out(args...); }
template <class T> void out(std::initializer_list<T> a) { for (auto i : a) { cout << i << " "; } cout << endl; }
template <class T> void out(vector<vector<T>> a) { for (vector<T> i : a) out(i); }
template <class T> void out_(T a[], int l, int r) { for (int i = l; i <= r; i++) cout << a[i] << " "; cout << endl; }
void out() { cout << "OK" << endl; }
template <class T> void sort(vector<T>& a) { sort(a.begin(), a.end()); }
template <class T> void rever(vector<T>& a) { reverse(a.begin(), a.end()); }
template <class T> void uniq(vector<T>& a) { sort(a); a.erase(unique(a.begin(), a.end()), a.end()); }
template <class T> vector<T> set_int(vector<T> a, vector<T> b) { sort(a); sort(b); vector<T> res;
set_intersection(a.begin(), a.end(), b.begin(), b.end(), back_inserter(res)); return res; }
clock_t start_time; void start_timer() { start_time = clock(); }
double get_time() { return (double)(clock() - start_time) / CLOCKS_PER_SEC; }
#if __SIZEOF_INT128__ >= 16
typedef __int128 LL;
istream& operator>>(istream& in, __int128& a) { int64_t b; in >> b; a = b; return in; }
ostream& operator<<(ostream& out, const __int128 a) {
    unsigned __int128 b = a < 0 ? -a : a; char buf[128]; char* c = end(buf); do { --c; *c = "0123456789"[b % 10]; b /= 10; } while (b);
    if (a < 0) { --c; *c = '-'; } int64_t len = end(buf) - c; out.rdbuf()->sputn(c, len); return out;
}
#endif

// solve the problem or die trying
// do something, stay focused
// look for stupid bugs
// guess, slow, stress
// the solution is always simple

const int N = 2e5 + 10;
const int L = 21;

vector<int> g[N];
int tin[N];
int tout[N];
int up[N][L];
int timer = 1;
ll sz[N];
ll ans[N];
int to[N];
vec<int> all[N];

void init(int n) {
    forn(i, 0, n + 5) {
        g[i].cle();
        tin[i] = 0;
        tout[i] = 0;
        forn(j, 0, L - 1) {
            up[i][j] = 0;
        }
        sz[i] = 0;
        ans[i] = 0;
        to[i] = 0;
        all[i].cle();
    }
    timer = 1;
}

void dfs_lca(int v = 1, int p = 1) {
    tin[v] = timer++;
    up[v][0] = p;
    for (int i = 1; i < L; i++) {
        up[v][i] = up[up[v][i - 1]][i - 1];
    }
    sz[v] = 1;
    all[v].pb(v);
    for (int u : g[v]) {
        if (u != p) {
            dfs_lca(u, v);
            sz[v] += sz[u];
            if (v == 1) {
                to[1] = 1;
                for (int i : all[u]) {
                    to[i] = u;
                }
            }
            if (all[v].size() < all[u].size()) {
                swap(all[v], all[u]);
            }
            for (int i : all[u]) {
                all[v].pb(i);
            }
        }
    }
    tout[v] = timer - 1;
}

bool is_anc(int u, int v) {
    return tin[u] <= tin[v] && tin[v] <= tout[u];
}

int lca(int u, int v) {
    if (is_anc(u, v)) return u;
    if (is_anc(v, u)) return v;
    for (int i = L - 1; i >= 0; i--) {
        if (!is_anc(up[u][i], v)) u = up[u][i];
    }
    return up[u][0];
}

ll f(ll n) {
    return n * (n - 1) / 2;
}

void Solve() {
    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        init(n);
        forn(i, 1, n - 1) {
            int u, v;
            cin >> u >> v;
            u++;
            v++;
            g[u].pb(v);
            g[v].pb(u);
        }
        dfs_lca();
        to[1] = 1;
        ans[1] = f(n);
        ans[2] = f(n);
        for (int i : g[1]) {
            ans[2] -= f(sz[i]);
        }
        int l = 1;
        int r = 1;
        forn(i, 2, n) {
            int v = i;
            if (!is_anc(l, v) && !is_anc(v, l) && !is_anc(r, v) && !is_anc(v, r)) {
                break;
            }
            if (r == 1) swap(l, r);
            if (is_anc(r, v)) {
                r = v;
            }
            else if (is_anc(l, v) && !is_anc(v, r)) {
                l = v;
            }
            int L = to[l];
            int R = to[r];
            if (R == 1) {
                swap(l, r);
                swap(L, R);
            }
            if (lca(l, r) != 1) {
                break;
            }
            else if (L == 1) {
                ans[i + 1] = (sz[1] - sz[R]) * sz[r];
            }
            else {
                ans[i + 1] = sz[l] * sz[r];
            }
        }
        forn(i, 1, n + 1) {
            ans[i] -= ans[i + 1];
        }
        forn(i, 1, n + 1) {
            cout << ans[i] << " ";
        }
        cout << "\n";
    }
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
#ifdef LOCAL
    freopen("usr/share/man/man1/input.txt", "r", stdin);
#endif
    start_timer();
    Solve();
    return 0;
}

```