1527_D. MEX Tree
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. 
```python
import sys, math
import io, os
#data = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
#from bisect import bisect_left as bl, bisect_right as br, insort
#from heapq import heapify, heappush, heappop
from collections import defaultdict as dd, deque, Counter
#from itertools import permutations,combinations
def data(): return sys.stdin.readline().strip()
def mdata(): return list(map(int, data().split()))
def outl(var) : sys.stdout.write(' '.join(map(str, var))+'\n')
def out(var) : sys.stdout.write(str(var)+'\n')
#from decimal import Decimal
#from fractions import Fraction
#sys.setrecursionlimit(100000)
#INF = float('inf')
mod = 998244353

def dfs(graph, start=0):
    n = len(graph)

    dp = [0] * n
    visited, finished, par = [False] * n, [False] * n, [0] * n

    stack = [start]
    while stack:
        start = stack[-1]

        # push unvisited children into stack
        if not visited[start]:
            visited[start] = True
            for child in graph[start]:
                if not visited[child]:
                    par[child] = start
                    stack.append(child)

        else:
            stack.pop()

            # base case
            dp[start] += 1

            # update with finished children
            for child in graph[start]:
                if finished[child]:
                    dp[start] += dp[child]

            finished[start] = True

    return dp, par

for t in range(int(data())):
    n=int(data())
    tree = [[] for i in range(n)]
    for i in range(n-1):
        u,v = mdata()
        tree[u].append(v)
        tree[v].append(u)
    dp, par = dfs(tree)
    ans = [0]*(n+1)
    for u in tree[0]:
        ans[0] += (dp[u]*(dp[u]-1))//2
    s = set()
    s.add(0)
    p = 1
    while p!=0:
        s.add(p)
        p = par[p]
    for u in tree[0]:
        if u in s:
            k=u
            break
    n1, n2 = 0, 1
    ans[1] = (n*(n-1))//2 - ans[0] - dp[1]*(n-dp[k])
    flag = True
    for i in range(2,n):
        p = i
        while p not in s:
            s.add(p)
            p = par[p]
        if p==i:
            continue
        if p==n1:
            if n1!=0:
                ans[i] = dp[n2]*(dp[n1]-dp[i])
            else:
                ans[i] = dp[n2]*(dp[n1] - dp[k] - dp[i])
            n1 = i
        elif p==n2:
            if n1!=0:
                ans[i] = dp[n1] * (dp[n2] - dp[i])
            else:
                ans[i] = (dp[n1] - dp[k]) * (dp[n2] - dp[i])
            n2 = i
        else:
            if n1!=0:
                ans[i] = dp[n1]*dp[n2]
            else:
                ans[i] = (dp[n1] - dp[k])*dp[n2]
            flag = False
            break
    if len(s) == n and flag:
        ans[-1] = 1
    outl(ans)







```