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:
class RangeQuery:
    def __init__(self, data, func=min):
        self.func = func
        self._data = _data = [list(data)]
        i, n = 1, len(_data[0])
        while 2 * i <= n:
            prev = _data[-1]
            _data.append([func(prev[j], prev[j + i]) for j in range(n - 2 * i + 1)])
            i <<= 1
    def query(self, begin, end):
        depth = (end - begin).bit_length() - 1
        return self.func(self._data[depth][begin], self._data[depth][end - (1 << depth)])

class LCA:
    def __init__(self, root, graph):
        self.time = [-1] * len(graph)
        self.path = [-1] * len(graph)
        P = [-1] * len(graph)
        t = -1
        dfs = [root]
        while dfs:
            node = dfs.pop()
            self.path[t] = P[node]
            self.time[node] = t = t + 1
            for nei in graph[node]:
                if self.time[nei] == -1:
                    P[nei] = node
                    dfs.append(nei)
        self.rmq = RangeQuery(self.time[node] for node in self.path)
    def __call__(self, a, b):
        if a == b: return a
        a = self.time[a]
        b = self.time[b]
        if a > b: a, b = b, a
        return self.path[self.rmq.query(a, b)]

import sys,io,os
try:Z=io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
except:Z=lambda:sys.stdin.readline().encode()
Y=lambda:map(int,Z().split())
O=[]
for _ in range(int(Z())):
    n=int(Z());g=[[]for i in range(n)]
    for i in range(n-1):u,v=Y();g[u].append(v);g[v].append(u)
    L=LCA(0,g);e=[1,0];r=[0]*(n+1)
    c=[-1]*n;d=[0]*n;p=[-1]*n;q=[0]
    while q:
        v=q.pop()
        if c[v]==-1:
            c[v]=0
            for i in g[v]:
                if i!=p[v]:p[i]=v;q.append(i);c[v]+=1
        if c[v]==0:
            d[v]+=1
            if p[v]!=-1:
                d[p[v]]+=d[v];c[p[v]]-=1
                if c[p[v]]==0:q.append(p[v])
    u,w=p[1],1
    while u:u,w=p[u],u
    d[0]-=d[w];t=0
    for i in g[0]:
        v=d[i];r[0]+=(v*v-v)//2
        if i==w:v-=d[1]
        r[1]+=t*v+v;t+=v
    for i in range(2,n):
        v=L(i,e[0])
        if v==i:continue
        elif v==e[0]:r[i]=d[e[1]]*(d[v]-d[i]);e[0]=i;continue
        elif v!=0:r[i]=d[e[0]]*d[e[1]];break
        v=L(i,e[1])
        if v==i:continue
        elif v==e[1]:r[i]=d[e[0]]*(d[v]-d[i]);e[1]=i;continue
        r[i]=d[e[0]]*d[e[1]];break
    else:r[-1]=1
    O.append(' '.join(map(str,r)))
print('\n'.join(O))