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 sys


def readline():
    return map(int, input().split())


def solve():
    n = int(input())
    nbrs = [list() for __ in range(n)]
    for __ in range(n - 1):
        ai, bi = readline()
        ai -= 1
        bi -= 1
        nbrs[ai].append(bi)
        nbrs[bi].append(ai)
    to_delete = list()

    pos = 0
    parent = -1
    arr = list(nbrs[pos])  # copy
    stack = [(pos, parent, arr)]
    while stack:
        pos, parent, arr = stack[-1]
        if arr:
            child = arr.pop()
            if child != parent and len(nbrs[child]) > 1:
                pos, parent = child, pos
                stack.append((pos, parent, list(nbrs[pos])))
                continue
        else:
            stack.pop()
            if len(nbrs[pos]) > 2 and parent >= 0:
                nbrs[pos].remove(parent)
                nbrs[parent].remove(pos)
                to_delete.append((pos, parent))
            while len(nbrs[pos]) > 2:
                child = nbrs[pos].pop()
                nbrs[child].remove(pos)
                to_delete.append((pos, child))

    segments = list()
    is_tail = [False] * n
    for i in range(n):
        p = len(nbrs[i])
        assert p <= 2
        if p == 0:
            segments.append((i, i))
        if is_tail[i] or p != 1:
            continue
        pos, = nbrs[i]
        prev = i
        while len(nbrs[pos]) == 2:
            prev, pos = pos, sum(nbrs[pos]) - prev
        assert len(nbrs[pos]) == 1
        is_tail[pos] = True
        segments.append((i, pos))
    a, b = segments.pop()
    k = len(to_delete)
    assert k == len(segments)
    print(k)
    for ((x1, y1), (c, d)) in zip(to_delete, segments):
        print(x1 + 1, y1 + 1, b + 1, d + 1)
        b = c


def main():
    t = int(input())
    for __ in range(t):
        solve()


if __name__ == '__main__':
    main()