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. 

Solution (in CPP):

Solution:
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <bitset>

using namespace std;
#define ll long long
#define pi pair<int,int>
#define pll pair<ll,ll>
#define ld  long double
#define vi vector<int> 
#define vll vector<ll> 
#define vvll vector<vector<ll>> 
#define vvi vector<vector<int>> 
#define vs vector<string>
#define vpll vector<pll>
#define vpi vector<pi>
#define pb push_back
#define eb emplace_back

#define FOR(i, a, b) for(int i = (a); i < (b); i++)

const int INF = 1e9 + 7;
const long long MOD = 1e9 + 7;
class least_common_ancestors{
    public:
    const static bool do_tour = false;
    int max_depth;
    int dfs_timer;
    vector<vector<int>> g;
    vector<vector<int>> ancestor;
    vector<bool> visited;
    vector<int> depth;
    vector<int> en;
    vector<int> ex;
    vector<int> par;
    vector<int> tour;

    bool BUILT_LCA_TABLE = false;

    least_common_ancestors(){}

    least_common_ancestors(long long n){
        g.resize(n + 1);
        visited.resize(n + 1 , 0);
        depth.resize(n + 1 , 0);
        en.resize(n + 1, 0);
        ex.resize(n + 1, 0);
        par.resize(n + 1, -1);
        dfs_timer = 0;
        max_depth = ceil(log2(n));
        ancestor = vector<vector<int>>(max_depth + 1, vector<int>(n + 1 , -1));
    }
    void add_edge(int l, int r){
        g[l].push_back(r);
        g[r].push_back(l);
    }
    void do_dfs(int sr){
        visited[sr] = true;
        dfs_timer++;
        en[sr] = dfs_timer;
        if(do_tour)
            tour.push_back(sr);
        for(auto child : g[sr]){
            if(!visited[child]){
                ancestor[0][child] = sr;
                depth[child] = depth[sr] + 1;
                par[child] = sr; 
                do_dfs(child);
            }
        }
        dfs_timer++;
        ex[sr] = dfs_timer;
        if(do_tour)
            tour.push_back(sr);
    }

    void build_least_common_ancestors_table(){
        int n = (int) g.size() - 1;
        this->do_dfs(1);
        for(int d = 1; d <= max_depth; d++){
            for(int i = 1; i <= n; i++){
                if(ancestor[d - 1][i] != -1){
                    ancestor[d][i] = ancestor[d - 1][ancestor[d - 1][i]];
                }
            }
        }

        BUILT_LCA_TABLE = true;
    }

    /*walk d units starting from l*/
    int climb(int start , int walk_up_by){
        assert(BUILT_LCA_TABLE);
        int i = start;
        for(int dd = 0; (dd <= max_depth && i != -1); dd++){
            if((1 << dd) & walk_up_by) i = ancestor[dd][i];
        }
        return i;
    }
    /*API : find least_common_ancestors of i and j*/
    int get_least_common_ancestors(int i , int j){
        assert(BUILT_LCA_TABLE);
        if(depth[i] > depth[j]) i = climb(i , depth[i] - depth[j]);
        if(depth[j] > depth[i]) j = climb(j , depth[j] - depth[i]);
        assert(depth[j] == depth[i]);
        if(i == j) return i;
        for(int d = max_depth; d >= 0; --d){
            if(ancestor[d][i] != ancestor[d][j]){
                i = ancestor[d][i];
                j = ancestor[d][j];
            }
        }
        return ancestor[0][i];
    }
    /*O(1) check for ancestor*/
    bool isAncestor(int u , int v){
        assert(BUILT_LCA_TABLE);
        return (en[u] <= en[v] && ex[v] <= ex[u]);
    }

    /* get distance between any two vertices */
    int get_distance(int u , int v){
        assert(BUILT_LCA_TABLE);
        return depth[u] + depth[v] - 2 * depth[get_least_common_ancestors(u , v)];
    }
};

int ver(int x){
    return x + 1;
}


void dfs(int x, int p, vvi &g, vll &subtree){
    subtree[x] = 1;
    for(auto y : g[x]){
        if(y == p) continue;
        dfs(y , x , g, subtree);
        subtree[x] += subtree[y];
    }
}
void solve(){
    int n;
    cin >> n;

    vvi g(n + 1);

    least_common_ancestors lca(n);

    FOR(i , 1, n){
        int x , y;
        cin >> x >> y;

        g[x].pb(y);
        g[y].pb(x);
        lca.add_edge(ver(x), ver(y));
    }

    lca.build_least_common_ancestors_table();

    vll subtree(n + 1, 0);
    dfs(0 , -1, g, subtree);

    vll mex(n + 1, 0);

    for(auto child : g[0]){
        mex[0] += 1LL * subtree[child] * (subtree[child] - 1) / 2LL;
    }
    int a = 0 , b = 0; // end points of the current path
    bool further_zero = false;

    auto calc = [&](int u , int v){
        if(u == 0 && v == 0){
            return 1LL * n * (n - 1) / 2LL - mex[0];
        }
        if(v == 0) swap(u , v);

        ll sub_u = subtree[u];
        ll sub_v = subtree[v];
        if(u == 0){
            int up = lca.climb(ver(v), lca.get_distance(ver(v),ver(0)) - 1) - 1;
            sub_u -= subtree[up];
            return 1LL * sub_v * sub_u;
        } 
        return 1LL * sub_v * sub_u; 
    };

    FOR(i , 1 , n){
        if(b == 0) swap(a , b);
        if(lca.isAncestor(ver(i) , ver(a)) || lca.isAncestor(ver(i) , ver(b))){
            mex[i] = 0;
            continue;
        }
        if((a == 0 && lca.get_least_common_ancestors(ver(i),ver(b)) == ver(0)) || (a != 0 && lca.isAncestor(ver(a) , ver(i)))){
            ll val = calc(a, b);
            ll tval = calc(i , b);
            mex[i] = val - tval;
            a = i;
            continue;
        }

        if(lca.isAncestor(ver(b), ver(i))){
            ll val = calc(b , a);
            ll tval = calc(i, a);
            mex[i] = val - tval;
            b = i;
            continue;
        }
        // cout << "finally here for " << i << endl;
        mex[i] = calc(a , b);
        further_zero = true;
        break;
    }

    if(!further_zero){
        if(a != 0 && b != 0){
            mex[n] = 1LL * subtree[a] * subtree[b];
        } else if(a == 0){
            int one_child = lca.climb(ver(b) , lca.get_distance(ver(b),ver(0)) - 1) - 1;
            mex[n] = subtree[b] * (subtree[a] - subtree[one_child]);
        } else{
            assert(b == 0);
            int one_child = lca.climb(ver(a) , lca.get_distance(ver(a),ver(0)) - 1) - 1;
            mex[n] = subtree[a] * (subtree[b] - subtree[one_child]);            
        }
    }

    FOR(i , 0 , n + 1){
        if(i > 0) cout << ' ';
        cout << mex[i];
    }
    cout << '\n';
}

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

    int tt = 1;
    cin >> tt;

    #ifdef SIEVE
    construct();
    #endif

    #ifdef NCR
    compute_combinations_table(MOD);
    #endif

    #ifdef FACTORIALS
    compute_factorials(MOD);
    #endif

    for(int tc = 1; tc <= tt; tc++){
        // cout << "Case #" << tc << ": ";
        solve();
    }
}