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:
def leaf(f,u):
    if len(m[u])==1:
        return u
    else:
        for v in m[u]:
            if v!=f:
                ans=leaf(u,v)
                if ans:return ans                  
def cut():
    stack=[]
    stack.append([0,-1,leaf(-1,0)])
    while len(stack):
        a,*b=stack.pop()
        f,u=b
        if a==0:
            stack.append([1,f,u])
            for v in m[u]-{f}:
                stack.append([0,u,v])
        elif a==1:
            du=len(m[u])
            it=iter(m[u]-{f})
            if du>=3:
                while du>=4:
                    v=next(it)
                    ct.append((u+1,v+1))
                    m[v].remove(u)
                    m[u].remove(v)
                    du-=1
                if f!=-1:
                    ct.append((f+1,u+1))
                    m[u].remove(f)
                    m[f].remove(u)


def link():
    l=set()
    node=-1
    for i in range(n):
        if len(m[i])<=1:
            l.add(i)
    v=next(iter(l))
    l.discard(v)
    u=end(v)
    l.discard(u)
    while len(l)!=0:
        v=next(iter(l))
        l.discard(v)
        lk.append((u+1,v+1))
        u=end(v)
        l.discard(u)
def end(s):
    if len(m[s])==0:return s
    f=s
    s=next(iter(m[s]))
    while len(m[s])!=1:
        f,s=s,next(iter(m[s]-{f}))
    return s
for test in range(int(input())):
    n=int(input())
    m=[set() for i in range(n)]
    ct=[]
    lk=[]
    for i in range(n-1):
        a,b=(int(i)-1 for i in input().split())
        m[a].add(b);m[b].add(a)
    cut()
    link()
    op=zip(ct,lk)
    print(len(ct))
    for c,l in op:
        print(*c,*l)