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 PYTHON3):

Solution:
import sys;from collections import Counter;input = sys.stdin.readline
def tree_dfs(g, root=0):
    s = [root];d = [1] * len(g);order = []
    while s:p = s.pop();d[p] = 0;order.append(p);s += [node for node in g[p] if d[node]]
    return order
class LCA:
    def __init__(self,n,s,edge):
        self.logn=n.bit_length();self.parent=[n*[-1]for _ in range(self.logn)];self.dist=[0]*n;stack=[s];visited={s}
        for i in stack:
            for j in edge[i]:
                if j in visited:continue
                stack.append(j);       visited.add(j);     self.parent[0][j]=i;  self.dist[j]=self.dist[i]+1
                for k in range(1,self.logn):self.parent[k][j]=self.parent[k-1][self.parent[k-1][j]]
    def query(self,a,b):
        if self.dist[a]<self.dist[b]:a,b=b,a
        if self.dist[a]>self.dist[b]:
            for i in range(self.logn):
                if (self.dist[a]-self.dist[b])&(1<<i):a=self.parent[i][a]
        if a==b:return a
        for i in range(self.logn-1,-1,-1):
            if self.parent[i][a]!=self.parent[i][b]:  a=self.parent[i][a];   b=self.parent[i][b]
        return self.parent[0][a]
    def path_range(self,a,b):return self.dist[a]+self.dist[b]-2*self.dist[self.query(a,b)]
    def x_in_abpath(self,x,a,b):return self.path_range(a,x)+self.path_range(b,x)==self.path_range(a,b)
for _ in range(int(input())):
    n = int(input())
    g = [[] for _ in range(n)]
    for _ in range(n - 1): a, b = map(int, input().split()); g[a].append(b);  g[b].append(a)
    ans = [0] * (n + 1);    ans[0] = n * (n - 1) // 2;    order = tree_dfs(g);    d = [0] * n
    for v in order[::-1]:d[v] += (sum([d[node] for node in g[v]]) + 1)
    lca = LCA(n, 0, g);a, b = 0, 0
    for node in g[0]:
        a += d[node];  b += d[node] * d[node]
        if lca.query(node, 1) == node:   d[0] -= d[node]
    ans[1] = (a * a - b) // 2 + n - 1;   l, r = 0, 0
    for i in range(1, n):
        if lca.x_in_abpath(i, l, r):  ans[i + 1] = ans[i]; continue
        elif lca.query(i, l) == l and lca.query(i, r) == 0:   l = i
        elif lca.query(i, r) == r and lca.query(i, l) == 0:   r = i
        else:    break
        ans[i + 1] = d[l] * d[r]
    for i in range(n):ans[i] = ans[i] - ans[i + 1]
    print(*ans)