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,random,bisect
from collections import deque,defaultdict
from heapq import heapify,heappop,heappush
from itertools import permutations
from math import log,gcd

input = lambda :sys.stdin.buffer.readline()
mi = lambda :map(int,input().split())
li = lambda :list(mi())

INF = 10**17

def test(n):
    p = [i+1 for i in range(n)]
    random.shuffle(p)
    Edge = []
    for i in range(1,n):
        pv = random.randint(0,i-1)
        Edge.append((p[pv],p[i]))
    return Edge

def line(N):
    node = [i+2 for i in range(N-1)]
    random.shuffle(node)
    node = [1] + node

    edge=[]
    for i in range(1,N):
        edge.append((node[i-1],node[i]))

    return edge

def star(N):
    node = [i+1 for i in range(N)]
    random.shuffle(node)

    edge = []
    for i in range(1,N):
        if random.randint(0,9999)%2:
            edge.append((node[0],node[i]))
        else:
            edge.append((node[i],node[0]))

    return edge

for _ in range(int(input())):
    n = int(input())
    #Edge = test(n)
    edge = [[] for i in range(n)]
    for i in range(n-1):
        a,b = mi()
        edge[a-1].append(b-1)
        edge[b-1].append(a-1)

    deq = deque([0])
    parent = [-1]*n
    topo = []
    while deq:
        v = deq.popleft()
        topo.append(v)
        for nv in edge[v]:
            if nv!=parent[v]:
                parent[nv] = v
                deq.append(nv)

    topo = topo[::-1]
    dp = [[0,INF,INF] for v in range(n)]
    not_cut = [[None,-1,(-1,-1)] for v in range(n)]

    def merge(v,nv):
        a,b,c = dp[v]
        dp[v][0] += min(dp[nv]) + 1
        dp[v][1] += min(dp[nv]) + 1
        dp[v][2] += min(dp[nv]) + 1

        if b + min(dp[nv][0],dp[nv][1]) < dp[v][2]:
            not_cut[v][2] = (not_cut[v][1],nv)
            dp[v][2] = b + min(dp[nv][0],dp[nv][1])
        if a + min(dp[nv][0],dp[nv][1]) < dp[v][1]:
            not_cut[v][1] = nv
            dp[v][1] = a + min(dp[nv][0],dp[nv][1])



    for v in topo:
        for nv in edge[v]:
            if nv!=parent[v]:
                merge(v,nv)

    topo = topo[::-1]
    limit = [2 for v in range(n)]
    print(min(dp[0]))
    CUT = []
    _ADD = []
    for v in topo:
        if limit[v]==1:
            if dp[v][1] < dp[v][0]:
                for nv in edge[v]:
                    if nv!=parent[v]:
                        if nv!=not_cut[v][1]:
                            CUT.append((v,nv))
                        else:
                            limit[nv] = 1
            else:
                for nv in edge[v]:
                    if nv!=parent[v]:
                        CUT.append((v,nv))
        else:
            if dp[v][2] < dp[v][1]:
                a,b = -1,-1
                for nv in edge[v]:
                    if nv!=parent[v]:
                        if nv not in not_cut[v][2]:
                            CUT.append((v,nv))
                        else:
                            limit[nv] = 1
                            while not_cut[nv][1]!=-1:
                                if dp[nv][1] < dp[nv][0]:
                                    nv = not_cut[nv][1]
                                else:
                                    break
                            if a==-1:
                                a = nv
                            else:
                                b = nv
                _ADD.append((a,b))
            else:
                if dp[v][1] < dp[v][0]:
                    a,b = v,-1
                    for nv in edge[v]:
                        if nv!=parent[v]:
                            if nv!=not_cut[v][1]:
                                CUT.append((v,nv))
                            else:
                                limit[nv] = 1
                                while not_cut[nv][1]!=-1:
                                    if dp[nv][1] < dp[nv][0]:
                                        nv = not_cut[nv][1]
                                    else:
                                        break
                                b = nv
                    _ADD.append((a,b))
                else:
                    _ADD.append((v,v))
                    for nv in edge[v]:
                        if nv!=parent[v]:
                            CUT.append((v,nv))

    for i in range(len(_ADD)-1):
        a,b = _ADD[i]
        c,d = _ADD[i+1]
        u,v = CUT[i]
        print(u+1,v+1,b+1,c+1)

    assert len(CUT)==min(dp[0])
    assert len(CUT)==len(_ADD)-1