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 fast            ios_base::sync_with_stdio(false); cin.tie(NULL);
#define lli             long long int
#define ld              long double
#define pll             pair<lli,lli>
#define ve              vector<lli>
#define vep             vector<pll>
#define pb              push_back
#define mp              make_pair
#define mt              make_tuple
#define all(x)          (x).begin(),(x).end()
#define fr(i,a,n)       for(lli i=a;i<(n);i++)
#define frx(i,a,n)      for(lli i=a;i>(n);i--)
#define lb              lower_bound
#define ub              upper_bound
#define F               first
#define S               second
#define endl            '\n'
#define op(x)           cout<<x<<endl
#define db(x)           cout << "[ " << x << " ]" << endl
#define db2(x,y)        cout<<"[ " <<x<<" "<<y<< " ]" <<endl
#define parr(arr,a,n)   fr(u,a,n) cout<<arr[u]<<" "; cout<<endl
#define yes             cout<<"YES"<<endl
#define no              cout<<"NO"<<endl
#define mem(a,x)        memset(a,x,sizeof(a))
#define sz(a) 		    ((lli) a.size())

lli n;
vep v,rem;

lli dfs(lli root,ve adj[],lli par){
    ve tips;
    for(auto e:adj[root]){
        if(e!=par){
            lli temp=dfs(e,adj,root);
            if(temp==-1)continue;
            else if(sz(tips)<2){
                tips.pb(temp);
            }
            else{
                v.pb(mp(e,temp));
                rem.pb(mp(root,e));
            }
        }
    }
    lli temp=sz(tips);
    if(!par){
        if(temp==0)v.pb(mp(1,1));
        if(temp==1)v.pb(mp(tips[0],1));
        if(temp==2)v.pb(mp(tips[0],tips[1]));
        return 0;
    }
    if(temp==0)return root;
    if(temp==1)return tips[0];
    v.pb(mp(tips[0],tips[1]));
    if(par)rem.pb(mp(root,par));
    return -1;
}

void solve(){
    cin>>n;
    ve adj[n+5];
    v.clear();
    rem.clear();
    fr(i,1,n){
        lli u,v;
        cin>>u>>v;
        adj[u].pb(v);
        adj[v].pb(u);
    }
    dfs(1,adj,0);
    op(sz(rem));
    fr(i,0,sz(rem)){
        cout<<rem[i].F<<" "<<rem[i].S<<" "<<v[i].S<<" "<<v[i+1].F<<endl;
    }
}

int main(){
    fast;
    lli test=1;
    cin>>test;
    while(test--){
        solve();
    }
}