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 CPP):

Solution:
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
struct line
{
    int from;
    int to;
    int next;
};
struct line que[200005];
struct request
{
    int x1;
    int y1;
    int x2;
    int y2;
};
vector<request> ans;
int in[100005], cnt, headers[100005];
void add(int from,int to)
{
    cnt++;
    que[cnt].from = from;
    que[cnt].to = to;
    que[cnt].next = headers[from];
    headers[from] = cnt;
}
int dfs(int u,int father)
{
    int child = 0, farthest = u;
    for (int i = headers[u]; i;i=que[i].next)
        if(que[i].to!=father)
        {
            int res = dfs(que[i].to, u);
            if(res<0)
                continue;
            child++;
            if(child==1)
                farthest = res;
            else
            {
                if(child==2)
                {
                    ans.push_back((request){father, u, farthest, res});
                    farthest = -1;
                }
                else
                    ans.push_back((request){u, que[i].to, que[i].to, res});
            }
        }
    return farthest;
}
int main()
{
    int n, t, u, v;
    scanf("%d", &t);
    while(t--)
    {
        scanf("%d", &n);
        cnt = 0;
        for (int i = 1; i <= n;i++)
            headers[i] = in[i] = 0;
        ans.clear();
        for (int i = 1; i < n; i++)
        {
            scanf("%d%d", &u, &v);
            add(u, v);
            add(v, u);
            in[u]++;
            in[v]++;
        }
        int first = 0;
        for (int i = 1; i <= n;i++)
            if(in[i]==1)
            {
                first = i;
                break;
            }
        int second = dfs(first, first);
        printf("%d\n", ans.size());
        for (int i = 0; i < ans.size();i++)
        {
            printf("%d %d %d %d\n", ans[i].x1, ans[i].y1, second, ans[i].x2);
            second = ans[i].y2;
        }
    }
    return 0;
}