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;
typedef pair<int,int> pi;
typedef vector<int> vi;
typedef vector<pi> vpi;
#define pb emplace_back
#define f first 
#define s second
#define mp make_pair
#define SZ(x) (int)x.size()
#define ALL(x) x.begin(),x.end()

const int MAXN = 100100;

int a,b,c,T,N,K;
vi V[MAXN];
int dp1[MAXN];
int dp2[MAXN];
map<pi,bool> M;
vpi R,L,B;
int deg[MAXN];
pi ep[MAXN];

void query(int x,int p){
    int c=0;
    for(auto v:V[x])if(v!=p){
        ++c;
        query(v,x);
    }

    // option 1 you HAVE an up
    vi tx;
    dp1[x]=c;
    for(auto v:V[x])if(v!=p){
        dp1[x]+=dp2[v];
        tx.pb(dp1[v]-dp2[v]);
    }
    int W=dp1[x];
    sort(ALL(tx));
    // you have 1 down and 1 up
    if(c>0){
        dp1[x] = min(dp1[x],W+tx[0]-1);
    }

    // option 2 you do NOT have an up

    dp2[x]=c;
    for(auto v:V[x])if(v!=p){
        dp2[x]+=dp2[v];
    }
    W=dp2[x];
    // you have 1 down
    if(c>0){
        dp2[x] = min(dp2[x], W+tx[0]-1);
    }
    if(c>1){
        dp2[x]=min(dp2[x],W+tx[0]+tx[1]-2);
    }

    if(p==-1){
        dp1[x]=1e9;
    }
}

void resolve(int x,int p,int o){
    int l=0;int c=0;
    vpi tx;
    for(auto v:V[x])if(v!=p){
        l+=dp2[v];++c;
        tx.pb(dp1[v]-dp2[v],v);
    }
    sort(ALL(tx));
    // cerr<<x<<' '<<c+l<<'\n';

    if(o==1){
        // using option 1 - you have an up

        int d=c+l;
        if(d==dp1[x]){
            for(auto v:V[x])if(v!=p){
                R.pb(x,v);
                resolve(v,x,2); // no ups
            }
        }else{
            L.pb(x,tx[0].s);
            resolve(tx[0].s,x,1); // goes up 
            for(auto v:V[x])if(v!=p&&v!=tx[0].s){
                R.pb(x,v);
                resolve(v,x,2); // no ups
            }
        }
    }

    if (o == 2){ // you have no ups
        int d=c+l;
        if(d==dp2[x]){
            for(auto v:V[x])if(v!=p){
                R.pb(x,v);
                resolve(v,x,2); // no ups
            }
        }else if(d+tx[0].f-1 == dp2[x]){
            L.pb(x,tx[0].s);
            resolve(tx[0].s,x,1);
            for(auto v:V[x])if(v!=p&&v!=tx[0].s){
                R.pb(x,v);
                resolve(v,x,2); // no ups
            }
        }else{
            L.pb(x,tx[0].s);
            L.pb(x,tx[1].s);
            resolve(tx[1].s,x,1);
            resolve(tx[0].s,x,1);
            for(auto v:V[x])if(v!=p&&v!=tx[0].s&&v!=tx[1].s){
                R.pb(x,v);
                resolve(v,x,2); // no ups
            }
        }
    }
}

int main(){
    cin>>T;
    while(T--){
        cin>>N;M.clear();R.clear();
        L.clear();B.clear();
        for(int i=1;i<=N;++i){
            V[i].clear();
            dp1[i]=dp2[i]=0;
        }
        for(int i=1;i<N;++i){
            cin>>a>>b;
            V[a].pb(b);
            V[b].pb(a);
        }
        query(1,-1);
        cout<<dp2[1]<<'\n';
        resolve(1,-1,2);
        
        for(int i=1;i<=N;++i){
            ep[i]=mp(i,i);
        }
        for(auto i:L){
            int a=i.f;
            int b=i.s;
            int c=ep[a].f+ep[a].s-a;
            int d=ep[b].f+ep[b].s-b;
            ep[a]=ep[b]=mp(-1,-1);
            ep[c]=ep[d]=mp(c,d);
        }
        vi ww;
        // cerr<<SZ(ww)<<'\n';
        for(int i=1;i<=N;++i)if(ep[i].f==i)ww.pb(i);
        // cerr<<SZ(ww)<<'\n';
        for(int i=0;i<SZ(ww)-1;++i){
            B.pb(ep[ww[i]].s, ep[ww[i+1]].f);
        }
        assert(SZ(R)==SZ(B));
        for(int i=0;i<SZ(R);++i){
            cout<<R[i].f<<' '<<R[i].s<<' '<<B[i].f<<' '<<B[i].s<<'\n';
        }
    }
}