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 time

#start_time = time.time()
#def TIME_(): print(time.time()-start_time)

import os, sys
from io import BytesIO, IOBase
from types import GeneratorType
from bisect import bisect_left, bisect_right
from collections import defaultdict as dd, deque as dq, Counter as dc
import math, string, heapq as h
BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0
    def __init__(self, file):
        import os
        self.os = os
        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 = self.os.read(self._fd, max(self.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 = self.os.read(self._fd, max(self.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:
            self.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")

def getInt(): return int(input())
def getStrs(): return input().split()
def getInts(): return list(map(int,input().split()))
def getStr(): return input()
def listStr(): return list(input())
def getMat(n): return [getInts() for _ in range(n)]
def getBin(): return list(map(int,list(input())))
def isInt(s): return '0' <= s[0] <= '9'
def ceil_(a,b): return a//b + (a%b > 0)

MOD = 10**9 + 7

"""

"""

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 = getInt()
    G = [[] for _ in range(N)]
    deg = [0]*N
    par = [-1]*N
    for i in range(N-1):
        a, b = getInts()
        G[a-1].append(b-1)
        G[b-1].append(a-1)
    #to_remove = []
    to_add = []
    leaves = []
    removed = set()
    global count
    count = 0
    @bootstrap
    def dfs(node):
        global count
        children = 0
        for neigh in G[node]:
            if neigh != par[node]:
                par[neigh] = node
                yield dfs(neigh)
                if (node, neigh) not in removed: children += 1
        if children == 2:
            if par[node] != -1:
                #to_remove.append((par[node],node))
                count += 1
                removed.add((par[node],node))
        if children > 2:
            if par[node] != -1:
                count += 1
                removed.add((par[node],node))
            idx = len(G[node]) - 1
            while children > 2:
                if G[node][idx] == par[node]: idx -= 1
                #to_remove.append((node,G[node][idx]))
                count += 1
                while (node,G[node][idx]) in removed or G[node][idx] == par[node]:
                    idx -= 1
                removed.add((node,G[node][idx]))
                children -= 1
                idx -= 1
        yield
    dfs(0)
    ends = []
    used = [0]*N
    global flag
    @bootstrap
    def dfs2(node):
        global flag
        if flag: neighs = 1
        else: neighs = 0
        flag = True
        used[node] = 1
        for neigh in G[node]:
            if not used[neigh] and (node,neigh) not in removed and (neigh,node) not in removed:
                neighs += 1
                yield dfs2(neigh)
        if neighs == 1:
            ends.append(node)
        elif neighs == 0:
            ends.append(node)
            ends.append(node)
        yield
    for i in range(N):
        flag = False
        if not used[i]:
            
            dfs2(i)
    removed = list(removed)
    #print(removed)
    #print(ends)
    #print(len(ends))
    print(len(removed))
    j = 0
    for i in range(1,len(ends)-1,2):
        print(removed[j][0]+1,removed[j][1]+1,ends[i]+1,ends[i+1]+1)
        j += 1
    return
    
for _ in range(getInt()):
    #print(solve())
    solve()

#TIME_()