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
sys.setrecursionlimit(111111)
def dfs(x):
    tag[x] = 1
    q = []
    ql = -1
    tgs = [-1, -1]
    for v in lian[x]:
        if tag[v] == 0:
            gs[v] = dfs(v)
            if gs[v][0] == -1 and ql == -1:
                ql = v
            q.append(v)
    if len(q) == 0:
        return [-1, x]
    if ql == -1:
        for i in range(len(q)-1):
            v1 = q[i]
            v2 = q[i+1]
            ans[0] += 1
            res.append((v1, x, gs[v1][0], gs[v2][0]))
            gs[v2][0] = gs[v1][1]
        v = q[len(q)-1]
        ans[0] += 1
        res.append((v, x, gs[v][0], x))
        tgs = [-1, gs[v][1]]
    else:
        v2 = ql
        last = -1
        for i in range(len(q)):
            v1 = q[i]
            if gs[v1][0] != -1:
                ans[0] += 1 
                res.append((v1, x, gs[v1][0], gs[v2][1]))
                gs[v2][1] = gs[v1][1]
            else:
                last = v1
        for i in range(len(q)):
            v1 = q[i]
            if gs[v1][0] == -1 and v1 != v2 and v1 != last:
                ans[0] += 1 
                res.append((v1, x, v1, gs[v2][1]))
                gs[v2][1] = gs[v1][1]
        if last == v2:
            tgs = [-1, gs[v2][1]]
        else:
            tgs = [gs[v2][1], gs[last][1]]
    
    
    return tgs
                
        
            
            
        
        
    for i in range(len(q)-1):
        v = q[i][1]
        dus = q[i][0]
        if dus == 3:
            ans[0] += 1
            
 
            
for _ in range(int(input())):
    n = int(input())
    du = [0]*(n+1)
    lian = [[] for i in range(n+1)]
    tag = [0] * (n+1)
    res = []
    ans = [0]
    gs = [[-1,-1] for i in range(n+1)]
    for i in range(n-1):
        a,b = map(int, input().split())
        du[a] += 1
        du[b] += 1
        lian[a].append(b)
        lian[b].append(a)
    dfs(1)
    print(ans[0])
    for i in res:
        print(i[0],i[1],i[2],i[3])