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
input = sys.stdin.buffer.readline

for _ in range(int(input())):
    n = int(input())
    edges = [list(map(int,input().split())) for i in range(n-1)]

    adj = [set() for i in range(n+1)]

    for a,b in edges:
        adj[a].add(b)
        adj[b].add(a)

    operations = []
    #removed_edge = [0]*(n-1)

    visited = [0] * (n + 1)
    parent = [0]*(n+1)
    s = [1]
    while s:
        c = s[-1]

        if not visited[c]:
            visited[c] = 1

            for ne in adj[c]:
                if not visited[ne]:
                    parent[ne] = c
                    s.append(ne)
        else:
            if len(adj[c]) > 2:
                if parent[c]:
                    operations.append([c,parent[c]])
                    adj[parent[c]].remove(c)
                    adj[c].remove(parent[c])

                while len(adj[c]) > 2:
                    x = adj[c].pop()
                    adj[x].remove(c)
                    operations.append([x, c])

            s.pop()

    '''for i in range(n-1):
        a,b = edges[i]

        if len(adj[a]) > 2 and len(adj[b]) > 2:
            operations.append([a,b])
            adj[a].remove(b)
            adj[b].remove(a)
            removed_edge[i] = 1

    for i in range(n-1):
        a,b = edges[i]

        if not removed_edge[i]:
            if len(adj[a]) > 2:
                operations.append([a,b])
                adj[a].remove(b)
                adj[b].remove(a)

            if len(adj[b]) > 2:
                operations.append([a, b])
                adj[a].remove(b)
                adj[b].remove(a)
    '''

    endpoints = []

    visited = [0]*(n+1)
    for i in range(1,n+1):
        if not visited[i]:
            endpoints.append([])

            s = [i]
            while s:
                c = s[-1]

                if not visited[c]:
                    visited[c] = 1

                    if len(adj[c]) <= 1:
                        endpoints[-1].append(c)

                    for ne in adj[c]:
                        s.append(ne)
                else:
                    s.pop()

    assert(len(operations) == len(endpoints) -1)

    for i in range(len(endpoints)-1):
        if len(endpoints[i]) == 1:
            endpoints[i].append(endpoints[i][0])

        operations[i].extend([endpoints[i][1],endpoints[i+1][0]])

    print(len(operations))
    for operation in operations:
        print(*operation)