Problem: Nastia has an unweighted tree with n vertices and wants to play with it!

The girl will perform the following operation with her tree, as long as she needs:

  1. Remove any existing edge. 
  2. Add an edge between any pair of vertices. 



What is the minimum number of operations Nastia needs to get a bamboo from a tree? A bamboo is a tree in which no node has a degree greater than 2.

Input

The first line contains a single integer t (1 ≤ t ≤ 10 000) — the number of test cases.

The first line of each test case contains a single integer n (2 ≤ n ≤ 10^5) — the number of vertices in the tree.

Next n - 1 lines of each test cases describe the edges of the tree in form a_i, b_i (1 ≤ a_i, b_i ≤ n, a_i ≠ b_i).

It's guaranteed the given graph is a tree and the sum of n in one test doesn't exceed 2 ⋅ 10^5.

Output

For each test case in the first line print a single integer k — the minimum number of operations required to obtain a bamboo from the initial tree.

In the next k lines print 4 integers x_1, y_1, x_2, y_2 (1 ≤ x_1, y_1, x_2, y_{2} ≤ n, x_1 ≠ y_1, x_2 ≠ y_2) — this way you remove the edge (x_1, y_1) and add an undirected edge (x_2, y_2).

Note that the edge (x_1, y_1) must be present in the graph at the moment of removing.

Example

Input


2
7
1 2
1 3
2 4
2 5
3 6
3 7
4
1 2
1 3
3 4


Output


2
2 5 6 7
3 6 4 5
0

Note

Note the graph can be unconnected after a certain operation.

Consider the first test case of the example: 

<image> The red edges are removed, and the green ones are added.

Solution (in PYTHON3):

Solution:
import io
import os
from collections import defaultdict
from types import GeneratorType

from heapq import heappush, heappop


# From https://github.com/cheran-senthil/PyRival/blob/master/pyrival/misc/bootstrap.py
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, edges):
    graph = [[] for i in range(N)]
    for (u, v) in edges:
        graph[u].append(v)
        graph[v].append(u)
    dp1 = [0] * N
    dp2 = [0] * N
    bp1 = [()] * N  # back pointers
    bp2 = [()] * N

    @bootstrap
    def dfs(node, p):
        for child in graph[node]:
            if child != p:
                yield dfs(child, node)

        total = 0  # total if connected with no children
        heap = []  # sorted connectable children
        for child in graph[node]:
            if child != p:
                total += dp2[child]
                heappush(heap, (dp2[child] - dp1[child], child))
        if heap:
            # Connect with 1 child
            gain1, child1 = heappop(heap)
            gain1 *= -1
            score1 = 1 + total + gain1
            if dp1[node] < score1:
                dp1[node] = score1
                bp1[node] = (child1,)
            if dp2[node] < score1:
                dp2[node] = score1
                bp2[node] = (child1,)
            if heap:
                # Connect with 2 children
                gain2, child2 = heappop(heap)
                gain2 *= -1
                assert gain2 <= gain1
                score2 = 2 + total + gain1 + gain2
                if dp2[node] < score2:
                    dp2[node] = score2
                    bp2[node] = (child1, child2)
        assert dp1[node] <= dp2[node]
        yield

    dfs(0, -1)
    disconnect = []

    @bootstrap
    def dfs2(node, p, isConnected):
        if not isConnected and dp1[node] < dp2[node]:
            connectedChild = bp2[node]
        else:
            connectedChild = bp1[node]

        for child in graph[node]:
            if child != p:
                childConnected = child in connectedChild
                if not childConnected:
                    disconnect.append((node, child))
                yield dfs2(child, node, childConnected)
        yield

    dfs2(0, -1, False)

    # Construct the paths
    disconnect = set(disconnect)
    uf = UnionFind(N)
    degree = [0] * N
    for u, v in edges:
        if (u, v) in disconnect or (v, u) in disconnect:
            continue
        degree[u] += 1
        degree[v] += 1
        uf.union(u, v)
    paths = defaultdict(list)
    for u in range(N):
        if degree[u] <= 1:
            paths[uf.find(u)].append(u)
    endpoints = list(paths.values())

    # Join the endpoints
    ops = []
    for i in range(len(endpoints) - 1):
        x = endpoints[i][-1]
        y = endpoints[i + 1][0]
        u, v = disconnect.pop()
        ops.append(" ".join(str(i + 1) for i in [u, v, x, y]))
    assert not disconnect
    assert len(ops) == N - 1 - max(dp1[0], dp2[0])
    return str(len(ops)) + "\n" + "\n".join(ops)


class UnionFind:
    def __init__(self, N):
        # Union find with component size
        # Negative means is a root where value is component size
        # Otherwise is index to parent
        self.p = [-1 for i in range(N)]

    def find(self, i):
        # Find root with path compression
        if self.p[i] >= 0:
            self.p[i] = self.find(self.p[i])
            return self.p[i]
        else:
            return i

    def union(self, i, j):
        # Union by size
        root1 = self.find(j)
        root2 = self.find(i)
        if root1 == root2:
            return
        size1 = -self.p[root1]
        size2 = -self.p[root2]
        if size1 < size2:
            self.p[root1] = root2
            self.p[root2] = -(size1 + size2)
        else:
            self.p[root2] = root1
            self.p[root1] = -(size1 + size2)

    def getComponentSize(self, i):
        return -self.p[self.find(i)]


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) - 1 for x in input().split()] for i in range(N - 1)]
        ans = solve(N, edges)
        print(ans)