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:
'''
from bisect import bisect,bisect_left

from collections import *
from heapq import *
from math import gcd,ceil,sqrt,floor,inf

from itertools import *
from operator import add,mul,sub,xor,truediv,floordiv
from functools import *'''

#------------------------------------------------------------------------
import os
import sys

from io import BytesIO, IOBase
# region fastio
 
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")
 

#------------------------------------------------------------------------
def RL(): return map(int, sys.stdin.readline().split())
def RLL(): return list(map(int, sys.stdin.readline().split()))
def N(): return int(input())
def A(n):return [0]*n
def AI(n,x): return [x]*n
def A2(n,m): return [[0]*m for i in range(n)]
def G(n): return [[] for i in range(n)]
def GP(it): return [[ch,len(list(g))] for ch,g in groupby(it)]
#------------------------------------------------------------------------


from types import GeneratorType
 
 
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

mod=10**9+7
farr=[1]
ifa=[]
 
def fact(x,mod=0):
    if mod:
        while x>=len(farr):
            farr.append(farr[-1]*len(farr)%mod)
    else:
        while x>=len(farr):
            farr.append(farr[-1]*len(farr))
    return farr[x]
 
def ifact(x,mod):
    global ifa
    fact(x,mod)
    ifa.append(pow(farr[-1],mod-2,mod))
    for i in range(x,0,-1):
        ifa.append(ifa[-1]*i%mod)
    ifa.reverse()
 
def per(i,j,mod=0):
    if i<j: return 0
    if not mod:
        return fact(i)//fact(i-j)
    return farr[i]*ifa[i-j]%mod
    
def com(i,j,mod=0):
    if i<j: return 0
    if not mod:        
        return per(i,j)//fact(j)
    return per(i,j,mod)*ifa[j]%mod
 
def catalan(n):
    return com(2*n,n)//(n+1)
 
def isprime(n):
    for i in range(2,int(n**0.5)+1):
        if n%i==0:
            return False
    return True

def floorsum(a,b,c,n):#sum((a*i+b)//c for i in range(n+1))
    if a==0:return b//c*(n+1)
    if a>=c or b>=c: return floorsum(a%c,b%c,c,n)+b//c*(n+1)+a//c*n*(n+1)//2
    m=(a*n+b)//c
    return n*m-floorsum(c,c-b-1,a,m-1)

def inverse(a,m):
    a%=m
    if a<=1: return a
    return ((1-inverse(m,a)*m)//a)%m
 
def lowbit(n):
    return n&-n
 
class BIT:
    def __init__(self,arr):
        self.arr=arr
        self.n=len(arr)-1
        
    def update(self,x,v):
        while x<=self.n:
            self.arr[x]+=v
            x+=x&-x
 
    def query(self,x):
        ans=0
        while x:
            ans+=self.arr[x]
            x&=x-1
        return ans

class ST:
    def __init__(self,arr):#n!=0
        n=len(arr)
        mx=n.bit_length()#取不到
        self.st=[[0]*mx for i in range(n)]
        for i in range(n):
            self.st[i][0]=arr[i]
        for j in range(1,mx):
            for i in range(n-(1<<j)+1):
                self.st[i][j]=max(self.st[i][j-1],self.st[i+(1<<j-1)][j-1])
    def query(self,l,r):
        if l>r:return -inf
        s=(r+1-l).bit_length()-1
        return max(self.st[l][s],self.st[r-(1<<s)+1][s])
        
class DSU:#容量+路径压缩
    def __init__(self,n):
        self.c=[-1]*n
 
    def same(self,x,y):
        return self.find(x)==self.find(y)
 
    def find(self,x):
        if self.c[x]<0:
            return x
        self.c[x]=self.find(self.c[x])
        return self.c[x]
 
    def union(self,u,v):
        u,v=self.find(u),self.find(v)
        if u==v:
            return False
        if self.c[u]>self.c[v]:
            u,v=v,u
        self.c[u]+=self.c[v]
        self.c[v]=u
        return True
 
    def size(self,x): return -self.c[self.find(x)]
    
class UFS:#秩+路径
    def __init__(self,n):
        self.parent=[i for i in range(n)]
        self.ranks=[0]*n
 
    def find(self,x):
        if x!=self.parent[x]:
            self.parent[x]=self.find(self.parent[x])
        return self.parent[x]
 
    def union(self,u,v):
        pu,pv=self.find(u),self.find(v)
        if pu==pv:
            return False
        if self.ranks[pu]>=self.ranks[pv]:
            self.parent[pv]=pu
            if self.ranks[pv]==self.ranks[pu]:
                self.ranks[pu]+=1
        else:
            self.parent[pu]=pv

class UF:#秩+路径+容量，边数
    def __init__(self,n):
        self.parent=[i for i in range(n)]
        self.ranks=[0]*n
        self.size=AI(n,1)
        self.edge=A(n)
 
    def find(self,x):
        if x!=self.parent[x]:
            self.parent[x]=self.find(self.parent[x])
        return self.parent[x]
 
    def union(self,u,v):
        pu,pv=self.find(u),self.find(v)
        if pu==pv:
            self.edge[pu]+=1
            return False
        if self.ranks[pu]>=self.ranks[pv]:
            self.parent[pv]=pu
            self.edge[pu]+=self.edge[pv]+1
            self.size[pu]+=self.size[pv]
            if self.ranks[pv]==self.ranks[pu]:
                self.ranks[pu]+=1
        else:
            self.parent[pu]=pv
            self.edge[pv]+=self.edge[pu]+1
            self.size[pv]+=self.size[pu]
 
def Prime(n):
    c=0
    prime=[]
    flag=[0]*(n+1) 
    for i in range(2,n+1):
        if not flag[i]:
            prime.append(i)
            c+=1
        for j in range(c):
            if i*prime[j]>n: break
            flag[i*prime[j]]=prime[j]
            if i%prime[j]==0: break
    return flag
 
def dij(s,graph):
    d=AI(n,inf)
    d[s]=0
    heap=[(0,s)]
    vis=A(n)
    while heap:
        dis,u=heappop(heap)
        if vis[u]:
            continue
        vis[u]=1
        for v,w in graph[u]:
            if d[v]>d[u]+w:
                d[v]=d[u]+w
                heappush(heap,(d[v],v))
    return d

def bell(s,g):#bellman-Ford
    dis=AI(n,inf)
    dis[s]=0
    for i in range(n-1):
        for u,v,w in edge:
            if dis[v]>dis[u]+w:
                dis[v]=dis[u]+w
    change=A(n)
    for i in range(n):
        for u,v,w in edge:
            if dis[v]>dis[u]+w:
                dis[v]=dis[u]+w
                change[v]=1
    return dis

def lcm(a,b): return a*b//gcd(a,b)
def lis(nums):
    res=[]
    for k in nums:
        i=bisect.bisect_left(res,k)
        if i==len(res):
            res.append(k)
        else:
            res[i]=k
    return len(res)

def RP(nums):#逆序对
    n = len(nums)
    s=set(nums)
    d={}
    for i,k in enumerate(sorted(s),1):
        d[k]=i
    bi=BIT([0]*(len(s)+1))
    ans=0
    for i in range(n-1,-1,-1):
        ans+=bi.query(d[nums[i]]-1)
        bi.update(d[nums[i]],1)
    return ans
 
class DLN:
    def __init__(self,val):
        self.val=val
        self.pre=None
        self.next=None

def nb(i,j,n,m):
    for ni,nj in [[i+1,j],[i-1,j],[i,j-1],[i,j+1]]:
        if 0<=ni<n and 0<=nj<m:
            yield ni,nj

def topo(n):
    q=deque()
    res=[]
    for i in range(1,n+1):
        if ind[i]==0:
            q.append(i)
            res.append(i)
    while q:
        u=q.popleft()
        for v in g[u]:
            ind[v]-=1
            if ind[v]==0:
                q.append(v)
                res.append(v)
    return res

@bootstrap
def gdfs(r,p):
    for ch in g[r]:
        if ch!=p:
            yield gdfs(ch,r)
    yield None


#from random import randint

from heapq import *
@bootstrap
def dfs(r,p):
    s=0
    one=[]
    for ch in g[r]:
        if ch!=p:
            child[r].append(ch)
            yield dfs(ch,r)
            ma=max(dp[ch])
            s+=ma
            t1=dp[ch][1]
            if t1+1>ma:
                heappush(one,[ma-t1-1,ch])
    #print(r,one)
    if not one:
        dp[r]=[s,s,s]
    elif len(one)==1:
        v,ch=heappop(one)
        ma=max(dp[ch])
        for i in range(3):
            if dp[ch][i]==ma:
                break
        g1[r].append((ch,i))
        dp[r]=[s,s-v,s-v]
    else:
        v,ch=heappop(one)
        v2,ch2=heappop(one)
        ma=max(dp[ch])
        for i in range(3):
            if dp[ch][i]==ma:
                break
        g1[r].append((ch,i))
        g2[r].append((ch,i))
        ma2=max(dp[ch2])
        for i in range(3):
            if dp[ch2][i]==ma2:
                break
        g2[r].append((ch2,i))
        dp[r]=[s,s-v,s-v-v2]
    yield None

@bootstrap
def dfs2(r,t):
    used=set()
    #print(r,t)
    if t==1:
        #print(r)
        ch,i=g1[r][0]
        used.add(ch)
        x,y=r,ch
        if x>y:
            x,y=y,x
        nedge.add((x,y))
        yield dfs2(ch,i)
    elif t==2:
        for ch,i in g2[r]:
            used.add(ch)
            x,y=r,ch
            if x>y:
                x,y=y,x
            nedge.add((x,y))
            yield dfs2(ch,i)
    for ch in child[r]:
        if ch not in used:
            ma=max(dp[ch])
            for i in range(3):
                if dp[ch][i]==ma:
                    break
            #print(r,ch,i)
            yield dfs2(ch,i)
    yield None


t=N()
for i in range(t):
    n=N()
    g=G(n)
    edge=[]
    for i in range(n-1):
        a,b=RL()
        a-=1
        b-=1
        g[a].append(b)
        g[b].append(a)
        if a>b:
            a,b=b,a
        edge.append((a,b))
    g1=G(n)
    g2=G(n)
    dp=[[0]*3 for i in range(n)]
    child=G(n)
    dfs(0,-1)
    ma=max(dp[0])
    for i in range(3):
        if dp[0][i]==ma:
            break
    nedge=set()
    #print(dp,i)
    #print(g1)
    #print(g2)
    dfs2(0,i)
    delt=[]
    add=[]
    for x,y in edge:
        if (x,y) not in nedge:
            delt.append((x,y))
    na=G(n)
    #ind=A(n)
    for x,y in nedge:
        na[x].append(y)
        na[y].append(x)
    #print(nedge,na)
    vis=A(n)
    for i in range(n):
        if len(na[i])==0:
            add.append((i,i))
        elif len(na[i])==1 and not vis[i]:
            #print(i)
            u=i
            vis[u]=1
            v=na[u][0]
            while len(na[v])!=1:
                #print(i,v)
                for ch in na[v]:
                    if ch!=i:
                        i,v=v,ch
                        
                        #print(i,v)
                        break
                
            add.append((u,v))
            vis[v]=1
            #print(u,v,vis)
    #print(add,delt)
            
    i=0
    print(len(delt))
    for i in range(len(delt)):
        x2,y2=add[i][1],add[i+1][0]
        x1,y1=delt[i]
        print(x1+1,y1+1,x2+1,y2+1)
        
        
    
'''
sys.setrecursionlimit(200000)
import threading
threading.stack_size(10**8)
t=threading.Thr
ead(target=main)
t.start()
t.join()
'''