// I_Love_LPL
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
const int N = 400005;
long long mod = 1e9 + 7;
const int lim = 4e5 + 5;
const int lg = 18;
const int base = 311;
const long double eps = 1e-6;
bool flag = 1;
ll timer = 0;
ll sz[N], dep[N], dp[N][lg + 1], tin[N], tout[N], gr[N];
vector<ll> node[N];
void dfs(ll u, ll p){
    sz[u] = 1;
    for (int i = 1; i <= lg; i++){
        dp[u][i] = dp[dp[u][i - 1]][i - 1];
    }
    timer++;
    tin[u] = timer;
    for (auto j : node[u]){
        if (j == p) continue;
        dep[j] = dep[u] + 1;
        dp[j][0] = u;
        dfs(j, u);
        sz[u] += sz[j];
    }
    timer++;
    tout[u] = timer;
}
bool in(ll u, ll v){
    return ((tin[u] <= tin[v]) && (tout[u] >= tout[v]));
}
ll get(ll u, ll d){
    for (int i = 0; i <= lg; i++){
        if (d & (1 << i)){
            u = dp[u][i];
        }
    }
    return u;
}
ll ans(ll l, ll r){
    if (flag == 0) return 0;
    if (l == 1 && r == 1){
        ll cnt = 1, ans = 0;
        for (auto j : node[1]){
            ans = ans + cnt * sz[j];
            cnt += sz[j];
        }
        return ans;
    }
    if (r == 1){
        return sz[l] * (sz[1] - sz[get(l, dep[l] - dep[1] - 1)]);
    } else {
        return sz[l] * sz[r];
    }
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    if (fopen("tests.inp", "r")){
        freopen("tests.inp", "r", stdin);
        freopen("tests.out", "w", stdout);
    }
    ll t;
    cin >> t;
    while (t--){
        ll n;
        cin >> n;
        for (int i = 1; i <= n; i++){
            node[i].clear();
            dep[i] = 0;
            for (int j = 0; j <= lg; j++){
                dp[i][j] = 0;
            }
        }
        for (int i = 1; i < n; i++){
            ll u, v;
            cin >> u >> v;
            u++;
            v++;
            node[u].push_back(v);
            node[v].push_back(u);
        }
        dfs(1, 1);
        flag = 1;
        ll l = 1, r = 1;
        for (int i = 1; i <= n; i++){
            if (l == 1){
                l = i;
            } else {
                if (in(i, l)){

                } else if (in(l, i)){
                    l = i;
                } else if (in(get(l, dep[l] - dep[1] - 1), i)){
                    flag = 0;
                } else if (r == 1){
                    r = i;
                } else if (in(r, i)){
                    r = i;
                } else if (in(i, r)){

                } else if (in(get(r, dep[r] - dep[1] - 1), i)){
                    flag = 0;
                } else {
                    flag = 0;
                }
            }
            gr[i] = ans(l, r);
        }
        gr[0] = n * (n - 1) / 2;
        for (int i = 1; i <= n; i++){
            cout << gr[i - 1] - gr[i] << " ";
        }
        cout << gr[n];
        cout << endl;
    }
}
/*
Ans:

Out:
*/

### Prompt

Your challenge is to write a cpp solution 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
// I_Love_LPL
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
const int N = 400005;
long long mod = 1e9 + 7;
const int lim = 4e5 + 5;
const int lg = 18;
const int base = 311;
const long double eps = 1e-6;
bool flag = 1;
ll timer = 0;
ll sz[N], dep[N], dp[N][lg + 1], tin[N], tout[N], gr[N];
vector<ll> node[N];
void dfs(ll u, ll p){
    sz[u] = 1;
    for (int i = 1; i <= lg; i++){
        dp[u][i] = dp[dp[u][i - 1]][i - 1];
    }
    timer++;
    tin[u] = timer;
    for (auto j : node[u]){
        if (j == p) continue;
        dep[j] = dep[u] + 1;
        dp[j][0] = u;
        dfs(j, u);
        sz[u] += sz[j];
    }
    timer++;
    tout[u] = timer;
}
bool in(ll u, ll v){
    return ((tin[u] <= tin[v]) && (tout[u] >= tout[v]));
}
ll get(ll u, ll d){
    for (int i = 0; i <= lg; i++){
        if (d & (1 << i)){
            u = dp[u][i];
        }
    }
    return u;
}
ll ans(ll l, ll r){
    if (flag == 0) return 0;
    if (l == 1 && r == 1){
        ll cnt = 1, ans = 0;
        for (auto j : node[1]){
            ans = ans + cnt * sz[j];
            cnt += sz[j];
        }
        return ans;
    }
    if (r == 1){
        return sz[l] * (sz[1] - sz[get(l, dep[l] - dep[1] - 1)]);
    } else {
        return sz[l] * sz[r];
    }
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    if (fopen("tests.inp", "r")){
        freopen("tests.inp", "r", stdin);
        freopen("tests.out", "w", stdout);
    }
    ll t;
    cin >> t;
    while (t--){
        ll n;
        cin >> n;
        for (int i = 1; i <= n; i++){
            node[i].clear();
            dep[i] = 0;
            for (int j = 0; j <= lg; j++){
                dp[i][j] = 0;
            }
        }
        for (int i = 1; i < n; i++){
            ll u, v;
            cin >> u >> v;
            u++;
            v++;
            node[u].push_back(v);
            node[v].push_back(u);
        }
        dfs(1, 1);
        flag = 1;
        ll l = 1, r = 1;
        for (int i = 1; i <= n; i++){
            if (l == 1){
                l = i;
            } else {
                if (in(i, l)){

                } else if (in(l, i)){
                    l = i;
                } else if (in(get(l, dep[l] - dep[1] - 1), i)){
                    flag = 0;
                } else if (r == 1){
                    r = i;
                } else if (in(r, i)){
                    r = i;
                } else if (in(i, r)){

                } else if (in(get(r, dep[r] - dep[1] - 1), i)){
                    flag = 0;
                } else {
                    flag = 0;
                }
            }
            gr[i] = ans(l, r);
        }
        gr[0] = n * (n - 1) / 2;
        for (int i = 1; i <= n; i++){
            cout << gr[i - 1] - gr[i] << " ";
        }
        cout << gr[n];
        cout << endl;
    }
}
/*
Ans:

Out:
*/

```