#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <functional>
#include <cassert>

#define sz(a) (int)(a).size()
#define all(a) begin(a), end(a)

using namespace std;

using ll = long long;
using ull = unsigned long long;

vector<vector<int>> g;
vector<int> subtree;
vector<int> tin;
vector<int> tout;
int timer = 0;

void dfs(int v, int p) {
    tin[v] = ++timer;
    subtree[v] = 1;
    for (int u : g[v]) {
        if (u != p) {
            dfs(u, v);
            subtree[v] += subtree[u];
        }
    }
    tout[v] = ++timer;
}

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

void solve() {
    int n;
    cin >> n;

    g.assign(n, vector<int>());
    subtree.assign(n, 0);
    tin.assign(n, 0);
    tout.assign(n, 0);

    for (int i = 0; i < n - 1; ++i) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    dfs(0, -1);

    vector<ll> ans(n + 1);

    int subroot;

    ans[1] = n - 1 - subtree[1];

    for (int u : g[0]) {
        ans[0] += (ll)subtree[u] * (subtree[u] - 1) / 2;
        
        if (parent(u, 1)) {
            ans[1] += (ll)(subtree[u] - subtree[1]) * (subtree[0] - subtree[u]);
            subroot = u;
        }
        else {
            ans[1] += (ll)subtree[u] * (subtree[0] - subtree[u] - subtree[1]);
        }
    }

    ans[1] /= 2;

    int v, u;
    v = 0;
    u = 1;

    for (int i = 2; i < n; ++i) {
        if (v == 0) {
            if (parent(subroot, i)) {
                if (parent(u, i)) {
                    ans[i] = (ll)(subtree[u] - subtree[i]) * (subtree[0] - subtree[subroot]);
                    u = i;
                }
                else if (parent(i, u)) {
                    ans[i] = 0;
                }
                else {
                    ans[i] = (ll)(subtree[u]) * (subtree[0] - subtree[subroot]);
                    break;
                }
            }
            else {
                ans[i] = (ll)subtree[u] * (subtree[0] - subtree[subroot] - subtree[i]);
                v = i;
            }
        }
        else if (parent(v, i)) {
            ans[i] = (ll)subtree[u] * (subtree[v] - subtree[i]);
            v = i;
        }
        else if (parent(u, i)) {
            ans[i] = (ll)subtree[v] * (subtree[u] - subtree[i]);
            u = i;
        }
        else if (!parent(i, v) && !parent(i, u)) {
            ans[i] = (ll)subtree[v] * subtree[u];
            break;
        }
    }

    int leaves = count_if(all(g),[](const vector<int>& neighbours) {
        return sz(neighbours) == 1;
    });

    if (leaves == 2) {
        ans[n] = 1;
    }

    for (int i = 0; i <= n; ++i) {
        cout << ans[i] << " ";
    }
    cout << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);      

    int t;
    cin >> t;

    while (t--) {
        solve();
    }

    return 0;
}
### Prompt

Your task is to create 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
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <functional>
#include <cassert>

#define sz(a) (int)(a).size()
#define all(a) begin(a), end(a)

using namespace std;

using ll = long long;
using ull = unsigned long long;

vector<vector<int>> g;
vector<int> subtree;
vector<int> tin;
vector<int> tout;
int timer = 0;

void dfs(int v, int p) {
    tin[v] = ++timer;
    subtree[v] = 1;
    for (int u : g[v]) {
        if (u != p) {
            dfs(u, v);
            subtree[v] += subtree[u];
        }
    }
    tout[v] = ++timer;
}

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

void solve() {
    int n;
    cin >> n;

    g.assign(n, vector<int>());
    subtree.assign(n, 0);
    tin.assign(n, 0);
    tout.assign(n, 0);

    for (int i = 0; i < n - 1; ++i) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    dfs(0, -1);

    vector<ll> ans(n + 1);

    int subroot;

    ans[1] = n - 1 - subtree[1];

    for (int u : g[0]) {
        ans[0] += (ll)subtree[u] * (subtree[u] - 1) / 2;
        
        if (parent(u, 1)) {
            ans[1] += (ll)(subtree[u] - subtree[1]) * (subtree[0] - subtree[u]);
            subroot = u;
        }
        else {
            ans[1] += (ll)subtree[u] * (subtree[0] - subtree[u] - subtree[1]);
        }
    }

    ans[1] /= 2;

    int v, u;
    v = 0;
    u = 1;

    for (int i = 2; i < n; ++i) {
        if (v == 0) {
            if (parent(subroot, i)) {
                if (parent(u, i)) {
                    ans[i] = (ll)(subtree[u] - subtree[i]) * (subtree[0] - subtree[subroot]);
                    u = i;
                }
                else if (parent(i, u)) {
                    ans[i] = 0;
                }
                else {
                    ans[i] = (ll)(subtree[u]) * (subtree[0] - subtree[subroot]);
                    break;
                }
            }
            else {
                ans[i] = (ll)subtree[u] * (subtree[0] - subtree[subroot] - subtree[i]);
                v = i;
            }
        }
        else if (parent(v, i)) {
            ans[i] = (ll)subtree[u] * (subtree[v] - subtree[i]);
            v = i;
        }
        else if (parent(u, i)) {
            ans[i] = (ll)subtree[v] * (subtree[u] - subtree[i]);
            u = i;
        }
        else if (!parent(i, v) && !parent(i, u)) {
            ans[i] = (ll)subtree[v] * subtree[u];
            break;
        }
    }

    int leaves = count_if(all(g),[](const vector<int>& neighbours) {
        return sz(neighbours) == 1;
    });

    if (leaves == 2) {
        ans[n] = 1;
    }

    for (int i = 0; i <= n; ++i) {
        cout << ans[i] << " ";
    }
    cout << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);      

    int t;
    cin >> t;

    while (t--) {
        solve();
    }

    return 0;
}
```