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 io
import os

from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque
from heapq import heappush, heappop, heapify
from math import gcd, inf

# https://raw.githubusercontent.com/cheran-senthil/PyRival/master/pyrival/graphs/lca.py
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)
        self.depth = [0] * len(graph)
        P = [-1] * len(graph)
        t = -1
        dfs = [root]
        while dfs:
            node = dfs.pop()
            d = self.depth[node]
            self.path[t] = P[node]
            self.time[node] = t = t + 1
            for nei in graph[node]:
                if self.time[nei] == -1:
                    P[nei] = node
                    self.depth[nei] = d + 1
                    dfs.append(nei)

        self.rmq = RangeQuery(self.time[node] for node in self.path)
        self.P = P
        self.root = root
        self.graph = graph
        self.buildSubTreeCounts()

    def lca(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)]

    def dist(self, u, v):
        return self.depth[u] + self.depth[v] - 2 * self.depth[self.lca(u, v)]

    def getPath(self, a, b):
        assert a != b
        anc = self.lca(a, b)
        aPath = [a]
        while aPath[-1] != anc:
            aPath.append(self.P[aPath[-1]])

        bPath = [b]
        while bPath[-1] != anc:
            bPath.append(self.P[bPath[-1]])
        assert aPath[-1] == bPath[-1]
        aPath.pop()
        return aPath + bPath[::-1]

    def isPath(self, a, b, c):
        # Returns whether b in on path between a and c
        return self.dist(a, b) + self.dist(b, c) == self.dist(a, c)

    def buildSubTreeCounts(self):
        root = self.root
        graph = self.graph
        P = self.P
        self.subtreeCount = [0] * len(graph)
        N = len(graph)
        root = 0
        stack = [root]
        subTreeCount = [1] * N
        while stack:
            u = stack.pop()
            if u >= 0:
                stack.append(~u)
                p = P[u]
                for v in graph[u]:
                    if v != p:
                        stack.append(v)
            else:
                u = ~u
                p = P[u]
                if p != -1:
                    subTreeCount[p] += subTreeCount[u]
        self.subTreeCount = subTreeCount

    def getSubTreeCount(self, u, p):
        if p == self.P[u]:
            return self.subTreeCount[u]

        return len(self.graph) - self.subTreeCount[p]


def solve(N, edges):
    graph = [set() for i in range(N)]
    for u, v in edges:
        graph[u].add(v)
        graph[v].add(u)

    ans = [0] * (N + 1)

    tree = LCA(0, graph)
    pathSet = {0}
    path = deque([0])
    for j in range(1, N):
        if j in pathSet:
            ans[j + 1] = ans[j]
            continue
        # Next missing number is j, try to extend current path
        if tree.isPath(path[0], path[-1], j):
            branch = tree.getPath(path[-1], j)[1:]
            path.extend(branch)
            pathSet.update(branch)
        elif tree.isPath(path[-1], path[0], j):
            branch = tree.getPath(path[0], j)[1:]
            path.extendleft(branch)  # wtf?
            pathSet.update(branch)
        else:
            break

        frontCount = tree.getSubTreeCount(path[0], p=path[1])
        backCount = tree.getSubTreeCount(path[-1], p=path[-2])
        ans[j + 1] = frontCount * backCount

    # Number of paths not containing 0
    ans0 = 0
    for v in graph[0]:
        ans0 += tree.subTreeCount[v] * (tree.subTreeCount[v] - 1) // 2
    # Number of paths containing 0
    ans[1] = N * (N - 1) // 2 - ans0

    for i in range(1, N):
        ans[i] -= ans[i + 1]

    ans[0] = ans0

    if DEBUG:
        assert sum(ans) == N * (N - 1) // 2
        ans2 = [0] * (N + 1)
        for u in range(N):
            for v in range(u + 1, N):
                path = set(tree.getPath(u, v))
                for mex in range(0, N + 1):
                    if mex not in path:
                        ans2[mex] += 1
                        break
        print(ans)
        print(ans2)
        assert ans == ans2

    return " ".join(map(str, ans))


DEBUG = False
if DEBUG:

    def genTree(N):
        H = 32
        edges = []
        path = [1] * H
        for i in range(2, N + 1):
            H = 32 - random.getrandbits(32).bit_length()
            edges.append((path[H + 1], i))
            for j in range(H + 1):
                path[j] = i
        assert len(edges) == N - 1
        return edges

    def genLine(N):
        return [(i, i + 1) for i in range(1, N)]

    import random

    random.seed(0)
    for _ in range(10000000):
        N = random.randint(1, 10)
        remap = list(range(N))
        random.shuffle(remap)
        edges = [(remap[u - 1], remap[v - 1]) for u, v in genTree(N)]
        print(edges)
        ans = solve(N, edges)
        # print(ans, ans1)
        # assert ans == ans1

    exit()


if __name__ == "__main__":
    input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

    TC = int(input())
    for tc in range(1, TC + 1):
        (N,) = [int(x) for x in input().split()]
        edges = [[int(x) for x in input().split()] for i in range(N - 1)]  # 0 indexed
        ans = solve(N, edges)
        print(ans)