#include<bits/stdc++.h>
#define int long long 
using namespace std;
const int MAX = 2e5;
const int LOG = 18;
int lev[MAX+1];
int memo[MAX+1][LOG+1];


int n;
vector<vector<int>> adj; 
vector<int> parent;
vector<int> subtree_size;
vector<int> ans;
vector<bool> one_present;

void dfs(int u, int p){
    if(p == u) lev[u] = 0;
    memo[u][0] = p; 
    for (int i = 1; i <= LOG; i++) 
        memo[u][i] = memo[memo[u][i - 1]][i - 1]; 
    if(u == 1) one_present[u] = true;
    parent[u] = p;
    subtree_size[u] = 1;
    for(int v : adj[u]){
        if(v != p){
            lev[v] = lev[u] + 1;
            dfs(v, u);
            subtree_size[u] += subtree_size[v];
            one_present[u] = one_present[u] || one_present[v];
        }
    }
}


int lca(int u, int v){ 
    if (lev[u] < lev[v]) 
        swap(u, v); 
  
    for (int i = LOG; i >= 0; i--) 
        if ((lev[u] - pow(2, i)) >= lev[v]) 
            u = memo[u][i]; 
  
    if (u == v) 
        return u; 
  
    for (int i = LOG; i >= 0; i--) { 
        if (memo[u][i] != memo[v][i]) { 
            u = memo[u][i]; 
            v = memo[v][i]; 
        } 
    } 

    return memo[u][0]; 
}

int dist(int u, int v){
    int l = lca(u, v);
    return lev[u] + lev[v] - 2 * lev[l];
}


int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int t;
    cin >> t;
    while(t--){
        cin >> n;
        adj = vector<vector<int>>(n);
        parent = vector<int>(n);
        subtree_size = vector<int>(n);
        ans = vector<int>(n+1);
        one_present = vector<bool>(n);
        for(int i = 0; i < n-1; i++){
            int u, v;
            cin >> u >> v;
            adj[u].push_back(v);
            adj[v].push_back(u);
        }
        dfs(0, 0);
        for(int v : adj[0]){
            ans[0] += (subtree_size[v] * (subtree_size[v] - 1) / 2);
        }

        vector<int> sizes;
        for(int v : adj[0]){
            int x = subtree_size[v];
            if(one_present[v]) x -= subtree_size[1];
            sizes.push_back(x);
        }

        int sum = 0;
        for(int x : sizes) {
            // cout << x << ' ';
            sum += x;
        }
        // cout << '\n';
        for(int i = 0; i < sizes.size(); i++) {
            sum -= sizes[i];
            ans[1] += sizes[i] * (sum + 1);
        }
        // cout << ans[1] << '\n';
        set<int> mex_finder;
        for(int i = 1; i <= n; i++) mex_finder.insert(i);

        int end1 = 0, end2 = -1;
        int temp = 0;
        int child_selected = -1;
        while(true){
            int mex = *mex_finder.begin();
            // cout << mex << '\n';
            if(mex == n) break;

            int cur = mex;
            while(mex_finder.find(cur) != mex_finder.end()){
                mex_finder.erase(cur);
                cur = parent[cur];
            }
            

            if(end2 == -1){
                end2 = mex;
                for(int v : adj[0]){
                    if(mex_finder.find(v) == mex_finder.end()){
                        temp = subtree_size[0] - subtree_size[v];
                        child_selected = v;
                    }
                }
            }
            else{
                if(cur != end1 && cur != end2) break;
                if(cur == end1) end1 = mex;
                else end2 = mex;
            }

            int new_mex = *mex_finder.begin();
            int x = (end1 == 0 ? temp : subtree_size[end1]);
            int y = subtree_size[end2];

            bool exist_in_1 = false, exist_in_2 = false;

            if(new_mex < n){
                if(end1 == 0){
                    if(dist(0, new_mex) < dist(child_selected, new_mex)) exist_in_1 = true;
                }
                else{
                    if(dist(end1, new_mex) < dist(parent[end1], new_mex)) exist_in_1 = true;
                }
                if(dist(end2, new_mex) < dist(parent[end2], new_mex)) exist_in_2 = true;
            }

            if(exist_in_1){
                ans[new_mex] += (x - subtree_size[new_mex]) * y;
            }
            else if(exist_in_2){
                ans[new_mex] += x * (y - subtree_size[new_mex]);
            }
            else{
                ans[new_mex] += x * y;
            }
        }

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

    }
    
    
}

/*




*/



### 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
#include<bits/stdc++.h>
#define int long long 
using namespace std;
const int MAX = 2e5;
const int LOG = 18;
int lev[MAX+1];
int memo[MAX+1][LOG+1];


int n;
vector<vector<int>> adj; 
vector<int> parent;
vector<int> subtree_size;
vector<int> ans;
vector<bool> one_present;

void dfs(int u, int p){
    if(p == u) lev[u] = 0;
    memo[u][0] = p; 
    for (int i = 1; i <= LOG; i++) 
        memo[u][i] = memo[memo[u][i - 1]][i - 1]; 
    if(u == 1) one_present[u] = true;
    parent[u] = p;
    subtree_size[u] = 1;
    for(int v : adj[u]){
        if(v != p){
            lev[v] = lev[u] + 1;
            dfs(v, u);
            subtree_size[u] += subtree_size[v];
            one_present[u] = one_present[u] || one_present[v];
        }
    }
}


int lca(int u, int v){ 
    if (lev[u] < lev[v]) 
        swap(u, v); 
  
    for (int i = LOG; i >= 0; i--) 
        if ((lev[u] - pow(2, i)) >= lev[v]) 
            u = memo[u][i]; 
  
    if (u == v) 
        return u; 
  
    for (int i = LOG; i >= 0; i--) { 
        if (memo[u][i] != memo[v][i]) { 
            u = memo[u][i]; 
            v = memo[v][i]; 
        } 
    } 

    return memo[u][0]; 
}

int dist(int u, int v){
    int l = lca(u, v);
    return lev[u] + lev[v] - 2 * lev[l];
}


int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int t;
    cin >> t;
    while(t--){
        cin >> n;
        adj = vector<vector<int>>(n);
        parent = vector<int>(n);
        subtree_size = vector<int>(n);
        ans = vector<int>(n+1);
        one_present = vector<bool>(n);
        for(int i = 0; i < n-1; i++){
            int u, v;
            cin >> u >> v;
            adj[u].push_back(v);
            adj[v].push_back(u);
        }
        dfs(0, 0);
        for(int v : adj[0]){
            ans[0] += (subtree_size[v] * (subtree_size[v] - 1) / 2);
        }

        vector<int> sizes;
        for(int v : adj[0]){
            int x = subtree_size[v];
            if(one_present[v]) x -= subtree_size[1];
            sizes.push_back(x);
        }

        int sum = 0;
        for(int x : sizes) {
            // cout << x << ' ';
            sum += x;
        }
        // cout << '\n';
        for(int i = 0; i < sizes.size(); i++) {
            sum -= sizes[i];
            ans[1] += sizes[i] * (sum + 1);
        }
        // cout << ans[1] << '\n';
        set<int> mex_finder;
        for(int i = 1; i <= n; i++) mex_finder.insert(i);

        int end1 = 0, end2 = -1;
        int temp = 0;
        int child_selected = -1;
        while(true){
            int mex = *mex_finder.begin();
            // cout << mex << '\n';
            if(mex == n) break;

            int cur = mex;
            while(mex_finder.find(cur) != mex_finder.end()){
                mex_finder.erase(cur);
                cur = parent[cur];
            }
            

            if(end2 == -1){
                end2 = mex;
                for(int v : adj[0]){
                    if(mex_finder.find(v) == mex_finder.end()){
                        temp = subtree_size[0] - subtree_size[v];
                        child_selected = v;
                    }
                }
            }
            else{
                if(cur != end1 && cur != end2) break;
                if(cur == end1) end1 = mex;
                else end2 = mex;
            }

            int new_mex = *mex_finder.begin();
            int x = (end1 == 0 ? temp : subtree_size[end1]);
            int y = subtree_size[end2];

            bool exist_in_1 = false, exist_in_2 = false;

            if(new_mex < n){
                if(end1 == 0){
                    if(dist(0, new_mex) < dist(child_selected, new_mex)) exist_in_1 = true;
                }
                else{
                    if(dist(end1, new_mex) < dist(parent[end1], new_mex)) exist_in_1 = true;
                }
                if(dist(end2, new_mex) < dist(parent[end2], new_mex)) exist_in_2 = true;
            }

            if(exist_in_1){
                ans[new_mex] += (x - subtree_size[new_mex]) * y;
            }
            else if(exist_in_2){
                ans[new_mex] += x * (y - subtree_size[new_mex]);
            }
            else{
                ans[new_mex] += x * y;
            }
        }

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

    }
    
    
}

/*




*/



```