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