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;
 
#define pb push_back
#define ff first
#define ss second
#define rsi resize
 
#define er(x) cerr<<#x<<": "<<x<<" "<<endl;
#define er2(x, y) cerr<<#x<<": "<<x<<" | "<<#y<<": "<<y<<endl;
#define er3(x, y, z) cerr<<#x<<":" <<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl;
#define erar(a) {cerr<<#a<<" "; for(auto x : a) cerr<<x<<" "; cerr<<endl;}
 
#define int long long
#define vi vector<int>
#define pii pair<int,int>
#define mii map< int,int >
 
#define rep(i,a,b) for(i=a; i<b; i++)
#define repr(i,a,b) for(i=a; i>b; i--)
#define put(a,b) cout<<a<<b;
#define sz(a) (int)a.size()
#define all(v) v.begin(),v.end()
 
// struct node { int t,a,b; };
struct cmp { bool operator() ( int a,int b ) const
{return a>b;}};
int casect = 1;
 
#define inf LLONG_MAX
#define M 1000000007
#define N 500000
 
int n,m,k;
vector<vi> adj;
vector<vi> ans;

vi par;
vector<bool> vis;


pii process(int u)
{
    int i,j,v;
    
    if ( sz(adj[u]) == 0 ) return {u,u};
    if ( sz(adj[u]) == 1 )
    {
        v = adj[u][0];  
        pii t = process(v);
        if ( t.ff == v ) return {u,t.ss};
        else
        {
            ans.pb({u,v,u,t.ff});
            return {u,t.ss};
        }
    }
    
    vector<pii> a,b;
    vi bv;
    
    for(auto v : adj[u])
    {
        pii t = process(v);
        if ( t.ff == v ) a.pb(t);
        else { b.pb(t); bv.pb(v); }
    }
    
    rep(i,2,sz(a))
    {
        ans.pb({u,a[i].ff,a[i].ff,a[0].ss});
        a[0].ss = a[i].ss;
    }
    while(sz(a) > 2) a.pop_back();
    
    if (sz(a) == 0)
    {
        pii t = b[ sz(b)-1 ]; 
        v =  bv[ sz(b)-1 ]; bv.pop_back(); b.pop_back();
        
        
        ans.pb({u,v,u,t.ff});
        a.pb({t.ff,t.ss});
    }
    
    rep(i,0,sz(b))
    {
        pii t= b[i];
        v = bv[i];
        
        ans.pb({u,v,a[0].ss,t.ff});
        a[0].ss = t.ss;
    }
    
    if (sz(a)== 1) return {u,a[0].ss};
    else return { a[0].ss,a[1].ss};
}

void dfs(int u)
{
    vis[u] = true;
    for(auto v : adj[u])
    {
        if (vis[v]) continue;
        par[v] = u;
        dfs(v);
    }
}

void solve()
{
    int i,j,x,y,z,p,q;
    
    adj.clear();
    ans.clear();

    cin>>n;
    
    adj.resize(n+1);
    rep(i,0,n-1)
    {
        cin>>x>>y;
        adj[x].pb(y);
        adj[y].pb(x);
    }
    
    par.clear(); par.resize(n+1,1);
    vis.clear(); vis.resize(n+1,false);
    
    dfs(1);
    
    adj.clear();
    adj.resize(n+1);
    rep(i,2,n+1) adj[ par[i] ].pb(i);
    
    process(1);
    put(sz(ans),'\n')
    for(auto v : ans)
    {
        for(auto x : v) put(x, " ")
        put("",'\n')
    }
}
 
int32_t main()
{
 
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    int t = 1;
    
    cin>>t;
    // preprocess();
    while(t--)
    {
        // cout<<"Case #"<<casect<<": "; casect++;
    solve();}
 
}