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 scan(x) do{while((x=getchar())<'0'); for(x-='0'; '0'<=(_=getchar()); x=(x<<3)+(x<<1)+_-'0');}while(0)
char _;

#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)
#define ALL(a,n) a,a+n
#define ALLV(v) v.begin(),v.end()
#define SZ(v) ((int)v.size())
#define REP(i,n) for(int i=0; i<n; ++i)
#define FOR(i,a,b) for(int i=a; i<=int(b); ++i)
#define rFOR(i,a,b) for(int i=a; i>=int(b); --i)

typedef long long ll;
typedef pair<int,int> pii;

struct{

    int N;
    vector<vector<int>> graph;
    vector<ll> sz;
    vector<ll> ans;
    vector<int> par;
    bitset<200005> removed, inseq;

    void init(int n){
        N = n;
        graph = vector<vector<int>>(N);
        sz = vector<ll>(N, 0);
        ans = vector<ll>(N+1, 0);
        par = vector<int>(N, -1);
        removed.reset();
        inseq.reset();
        REP(_, N-1){
            int a, b;
            cin >> a >> b;
            graph[a].pb(b);
            graph[b].pb(a);
        }
        dfs1();
    }

    void dfs1(int n=0, int p=-1){
        par[n] = p;
        sz[n] = 1;
        for(int v : graph[n]){
            if(v==p) continue;
            dfs1(v, n);
            sz[n] += sz[v];
        }
    }

    int dfs2(int n, int& s1, int& s2){
        if(n==1){
            inseq[n] = 1;
            s2 = sz[n];
            return sz[n];
        }
        if(n==0){
            inseq[n] = 1;
            vector<ll> vals;
            ll sm = 0;
            for(int v : graph[n]){
                int cnt = dfs2(v, s1, s2);
                if(cnt==0){
                    vals.pb(sz[v]);
                    s1 += sz[v];
                }else{
                    vals.pb(sz[v]-cnt);
                }
                sm += vals.back();
            }
            ++s1;
            ans[1] = (sm * (sm+1))/2;
            for(ll x : vals){
                ans[1] -= (x * (x-1))/2;
            }
        }else{
            for(int v : graph[n]){
                if(v==par[n]) continue;
                int cnt = dfs2(v, s1, s2);
                if(cnt){
                    inseq[n] = 1;
                    dfs3(n);
                    return cnt;
                }
            }
        }
        return 0;
    }

    void dfs3(int n){
        if(removed[n]) return;
        if(!inseq[n]) removed[n] = 1;
        for(int v : graph[n]){
            if(v==par[n] || inseq[v]) continue;
            dfs3(v);
        }
    }

    void solve(){
        for(int v : graph[0]){
            ans[0] += (sz[v] * (sz[v] - 1)) / 2;
        }

        int e1 = 0, e2 = 1;
        int s1 = 0, s2 = 0;
        dfs2(0, s1, s2);

        // cerr << ans[0] << " " << ans[1] << "\n";
        // cerr << e1 << " " << s1 << ", " << e2 << " " << s2 << "\n";
        ans[N] = 1;
        FOR(i, 2, N-1){
            if(removed[i]){
                ans[i] = 1LL*s1*s2;
                ans[N] = 0;
                break;
            }
            if(inseq[i]){
                continue;
            }

            vector<int> seq;
            seq.pb(i);
            inseq[i] = 1;
            while(true){
                int p = par[seq.back()];
                if(inseq[p]) break;
                seq.pb(p);
                inseq[p] = 1;
            }
            if(par[seq.back()]==e1){
                dfs3(e1);
                ans[i] = s2*(s1-sz[i]);
                s1 = sz[i];
                e1 = i;
            }else{
                dfs3(e2);
                ans[i] = s1*(s2-sz[i]);
                s2 = sz[i];
                e2 = i;
            }
            // cerr << e1 << " " << s1 << ", " << e2 << " " << s2 << "\n";
            FOR(i, 1, SZ(seq)-1){
                dfs3(seq[i]);
            }
        }
    }

    void print_ans(){
        REP(i, N+1){
            if(i) cout << " ";
            cout << ans[i];
        }
        cout << "\n";
    }

} sol;

void solve(){
    int n; cin >> n;
    sol.init(n);
    sol.solve();
    sol.print_ans();
}

int main(){
    cin.sync_with_stdio(0);
    cin.tie(0);
    int tc; cin >> tc;
    REP(i, tc){
        solve();
    }
    return 0;
}