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;
const long long mod=1e9+7,INF=1e18;
#define ll long long 
#define line cout<<"\n";
#define flush cout<<endl;
#define pll pair<ll,ll>
#define x first
#define y second
#define p_all(arr) for(auto i:arr){cout<<i<<" ";}cout<<"\n";
vector<vector<ll> > tree;
vector<pair<pll,pll> > ans;
pll dfs(ll u,ll pa)
{
    vector<pll> temp;
    vector<ll> val;
    pll temp2;
    for(auto v:tree[u])
    {
        if(v!=pa)
        {
            temp2=dfs(v,u);
            val.push_back(v);
            temp.push_back(temp2);
        }
    }
    ll idx=-1;
    temp2={u,-1};
    if(temp.size()==0)
    return temp2;
    for(int i=0;i<temp.size();i++)
    {
        if(temp[i].y==-1)
        {
            idx=i;
            temp2=temp[i];
        }
    }
    if(idx==-1)
    {
        for(int i=0;i<temp.size();i++)
        {
            ans.push_back({{u,val[i]},{temp2.x,temp[i].x}});
            temp2={temp[i].y,-1};
        }
    }
    else
    {
        ll flag=-1;
        for(int i=0;i<temp.size();i++)
        if(i!=idx)
        {
            if(temp[i].y==-1)
            {
                if(flag==-1)
                {
                    flag=i;
                    continue;
                }
                ans.push_back({{u,val[i]},{temp2.x,val[i]}});
                temp2={temp[i].x,-1};
            }
            else
            {
                ans.push_back({{u,val[i]},{temp2.x,temp[i].x}});
                temp2={temp[i].y,-1};
            }
        }
        if(flag!=-1)
        {
            temp2={temp2.x,temp[flag].x};
        }
    }
    return temp2;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    ll t=1;
    cin>>t;
    for(ll test=1;test<=t;test++)
    {
        ll n;
        cin>>n;
        vector<vector<ll> > tree1;
        vector<pair<pll,pll> > ans1;
        ans=ans1;
        tree=tree1;
        tree.resize(n);
        ll u,v;
        for(int i=0;i<n-1;i++)
        {
            cin>>u>>v;
            u--,v--;
            tree[u].push_back(v);
            tree[v].push_back(u);
        }
        pll temp=dfs(0,-1);
        cout<<ans.size()<<"\n";
        for(int i=0;i<ans.size();i++)
        {
            cout<<ans[i].x.x+1<<" "<<ans[i].x.y+1<<" "<<ans[i].y.x+1<<" "<<ans[i].y.y+1<<"\n";
        }
    }
    return 0;
}