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)
        for node in g[p]:
            if d[node]:
                s.append(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]:
        for node in g[v]:
            d[v] += d[node]
        d[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)