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 <bits/stdc++.h>
using namespace std;

// #define int ll 
#define f first
#define s second
#define pb push_back
#define ar array
#define all(x) x.begin(), x.end()
#define siz(x) (int) x.size()
#define uid(a, b) uniform_int_distribution<int>(a, b)(rng)
#define FOR(i, a, b) for(auto i=(a); i<(b); i++)
#define ROF(i, a, b) for(auto i=(b)-1; i>=(a); i--)
#define F0R(i, n) FOR(i, 0, n)
#define R0F(i, n) ROF(i, 0, n)

using ll=long long;
using ld=long double;
using pii=pair<int, int>;
using pll=pair<ll, ll>;
using vi=vector<int>;
using vl=vector<ll>;
using vpii=vector<pii>;

template<class T> bool ckmin(T&a, const T&b) {return b<a?a=b,1:0;}
template<class T> bool ckmax(T&a, const T&b) {return b>a?a=b,1:0;}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int mxN=2e5+10;
const int MOD=1e9+7; 
const ll infLL=1e18;
const ld eps=1e-6;

void solve(){
    int N; cin >> N;
    vector<vi> adj(N); 
    F0R(i, N-1){
        int e1, e2; cin >> e1 >> e2;
        adj[e1].pb(e2);
        adj[e2].pb(e1); 
    }
    vi sz(N), tin(N), tout(N), anc(N), par(N); int tim=0;
    function<void(int, int)> dfs=[&](int u, int p){
        tin[u]=tim++;
        par[u]=p;
        for(auto v:adj[u]){
            if(v==p) continue;
            dfs(v, u);
            sz[u]+=sz[v];
        }
        sz[u]++;
        tout[u]=tim++;
    };
    function<void(int, int, int)> dfs_zero=[&](int u, int p, int c){
        anc[u]=c;
        for(auto v:adj[u]){
            if(v==p) continue;
            dfs_zero(v, u, c);
        }
    };
    auto is_anc=[&](int u, int p){
        if(tin[p]<tin[u]&&tout[u]<tout[p]) return 1;
        return 0;
    };
    dfs(0, -1);
    vl ans(N+1);
    for(auto c:adj[0]) 
        ans[0]+=(1LL*sz[c]*(sz[c]-1))/2;
    for(auto c:adj[0]) 
        dfs_zero(c, 0, c);
    vi vis(N); 
    // int mex=1;
    auto trav=[&](int i, int Y){
        int X=i;
        while(X!=Y){
            vis[X]=1;
            // while(vis[mex]&&mex<N) mex++;
            X=par[X];
        }
    };
    // F0R(i, N) cout << anc[i] << ' ';
    // cout << "\n";
    // F0R(i, N) cout << sz[i] << ' ';
    // cout << "\n";
    {
        ll p=0;
        trav(1, 0);
        for(auto c:adj[0]){
            int cur=sz[c];
            if(c==anc[1]){
                cur-=sz[1];
                sz[0]-=sz[c];
            }
            ans[1]+=p*cur;
            ans[1]+=cur;
            p+=cur;
        }
        // cout << "siz 0: " << sz[0] << "\n";
    }
    int X=0, Y=1;
    FOR(i, 2, N){
        if(vis[i])
            continue;
        if(is_anc(Y, X)) swap(X, Y);
        // cout << X << ' ' << Y << ' ' << i << endl;
        bool b=0;
        if(Y==0){
            if(anc[i]==anc[1]) b=1;
        }
        if(is_anc(i, X)){
            // cout << "CHK: " << i << ' ' << X << "\n";
            ans[i]+=1LL*(sz[X]-sz[i])*(sz[Y]);
            trav(i, X);
            X=i;
        }
        else if(is_anc(i, Y)&&b==0){
            // cout << "CHK: " << i << ' ' << Y << "\n";
            ans[i]+=1LL*(sz[Y]-sz[i])*sz[X];
            trav(i, Y);
            Y=i;
        }
        else{
            ans[i]+=1LL*sz[Y]*sz[X];
            break;
        }
    }
    {
        ll p=0;
        F0R(i, N+1){
            p+=ans[i];
        }
        ans[N]=1LL*N*(N-1)/2-p;
    }
    F0R(i, N+1) cout << ans[i] << ' ';
    cout << "\n";
}

int32_t main(){
    cin.tie(0)->sync_with_stdio(0);
    int t; cin >> t;
    while(t--) solve();    
    return 0; 
}