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<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+10;

struct edge
{
    int u,v;
};

vector< pair<int,int> >g[maxn];
int Isclear[maxn];
vector< pair<int,int> > cl,line;
void dfs(int p,int fa)
{
    int sz=g[p].size();
    if(p!=fa)
        sz--;
    for(auto x:g[p])
    {
        if(x.first==fa)
            continue;
        dfs(x.first,p);

        if(Isclear[x.first]!=-1)
            sz--,cl.push_back({p,x.first}),Isclear[x.first]=p;
    }

    if(sz>=2)
    {
        Isclear[p]=0;
        for(auto x:g[p])
        {
            if(sz<=2)
                break;
            if(x.first==fa)
                continue;
            if(Isclear[x.first]==-1)
                Isclear[x.first]=p,sz--,cl.push_back({p,x.first});
        }

    }
}
vector<int> cal;
bool used[maxn];
void dfs2(int p,int fa)
{
    int sz=0;
    used[p]=1;
    for(auto x:g[p])
    {
        if(x.first==fa)
            continue;
        if(Isclear[x.first]!=-1)
            continue;
        dfs2(x.first,p);
        sz++;
    }
    if(!sz)
        cal.push_back(p);
    else if(sz==1&&Isclear[p]==fa)
        cal.push_back(p);
}

void init(int n)
{
    for(int i=1; i<=n; i++)
    {
        g[i].clear();
        Isclear[i]=-1;
    }
    cl.clear();
    line.clear();
}
int main()
{
    int t;
    scanf("%d",&t);
    memset(Isclear,-1,sizeof(Isclear));
    while(t--)
    {
        int n;
        scanf("%d",&n);
        for(int i=1; i<n; i++)
        {
            int x,y;
            scanf("%d%d",&x,&y);
            g[x].push_back({y,i});
            g[y].push_back({x,i});
        }
        dfs(1,1);
        Isclear[1]=0;
        for(int i=1; i<=n; i++)
        {
            if(Isclear[i]!=-1)
            {

                dfs2(i,Isclear[i]);
                if(cal.size()==1)
                    line.push_back({cal[0],cal[0]});
                else
                    line.push_back({cal[0],cal[1]});
                cal.clear();
            }
        }
        vector<pair<int,int>> ans;
        for(int i=1; i<line.size(); i++)
        {
            ans.push_back({line[i-1].second,line[i].first});
        }
        printf("%d\n",cl.size());
        for(int i=0; i<cl.size(); i++)
        {
            printf("%d %d %d %d\n",cl[i].first,cl[i].second,ans[i].first,ans[i].second);
        }
        init(n);
    }
    return 0;
}
/*
15
1 20 9 37
23 34 11 38
30 23 15 10
30 10 10 13
30 22 13 31
30 32 9 2
1 30 29 25
1 6 17 21
19 24 21 4
1 19 22 7
14 16 35 24
5 13 24 26
1 5 18 32
1 33 32 28
1 21 33 34
*/