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 math
from bisect import bisect_left
import os
import sys
from io import BytesIO, IOBase
from types import GeneratorType
from collections import defaultdict
BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")

sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")
sys.setrecursionlimit(2*10**5)


def bootstrap(f, stack=[]):
    def wrappedfunc(*args, **kwargs):
        if stack:
            return f(*args, **kwargs)
        else:
            to = f(*args, **kwargs)
            while True:
                if type(to) is GeneratorType:
                    stack.append(to)
                    to = next(to)
                else:
                    stack.pop()
                    if not stack:
                        break
                    to = stack[-1].send(to)
            return to
    return wrappedfunc


def solve():
    n = int(input())
    MA = n + 1
    level = 25
    tree = [[] for i in range(MA)]
    depth = [0 for i in range(MA)]
    parent = [[0 for i in range(level)] for j in range(MA)]
    size = [1 for i in range(MA)]
    ans= [0 for i in range(MA)]

    @bootstrap
    def dfs(cur, prev):
        depth[cur] = depth[prev] + 1
        parent[cur][0] = prev
        for i in range(len(tree[cur])):
            if (tree[cur][i] != prev):
                yield dfs(tree[cur][i], cur)
                size[cur]+=size[tree[cur][i]]

        yield


    def precomputeSparseMatrix(n):
        for i in range(1, level):
            for node in range(n):
                if (parent[node][i - 1] != -1):
                    parent[node][i] = parent[parent[node][i - 1]][i - 1]

    def lca(u, v):
        if (depth[v] < depth[u]):
            u, v = v, u

        diff = depth[v] - depth[u]

        for i in range(level):
            if ((diff >> i) & 1):
                v = parent[v][i]

        if (u == v):
            return u

        i = level - 1
        while (i >= 0):

            if (parent[u][i] != parent[v][i]):
                u = parent[u][i]
                v = parent[v][i]

            i += -1

        return parent[u][0]

    def add(a, b):
        tree[a].append(b)
        tree[b].append(a)

    for j in range(n-1):
        u,v=map(int,input().split())
        add(u,v)

    dfs(0, -1)
    precomputeSparseMatrix(n)

    s1=0

    for j in tree[0]:
        ans[0]+=(size[j]*(size[j]-1))//2

        if lca(j,1)==j:
            s1=n-size[j]

    rem=n*(n-1)//2-ans[0]
    ans[1]=rem-s1*size[1]
    rem=s1*size[1]
    size[0]=s1
    u=1
    v=0

    for i in range(2,n):

        if v==0:
            val1=1
            p1=lca(u,i)
            p2=lca(v,i)
            if p1==u:
                u=i
            elif p1==i:
                pass
            elif p1==0:
                if lca(v,i)==v:
                    v=i
            else:
                val1=0


            if val1!=0:
                val1=size[u]*size[v]


            ans[i]=rem-val1
            rem=val1

        else:
            p1=lca(u,i)
            p2=lca(v,i)
            if p1==u:
                u=i
                val1 = size[u] * size[v]
            elif p2==v:
                v=i
                val1 = size[u] * size[v]

            elif p1==i:
                val1=size[u]*size[v]
            elif p2==i:
                val1 = size[u] * size[v]

            else:
                val1=0

            ans[i]=rem-val1
            rem=val1


        if rem==0:
            break

    ans[-1]=rem
    print(*ans)

















t=int(input())
for _ in range(t):
    solve()