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 int max_n=1e5+10;
vector<int> g[max_n],ans2[max_n];
typedef pair<int, int> P;
vector<P> ans1;
int root;
int dp[max_n][3];
bool cmp(int u,int v){
    return dp[u][1]-dp[u][2]<dp[v][1]-dp[v][2];
}
bool vis[max_n];
int dfs(int u,int fa,int num){
    if(g[u].size()==1){
        dp[u][num]=0;
        // if(!vis[u]){
        //     ans2.push_back(u);
        //     vis[u]=1;
        // }
        //cout<<u<<endl;
        return 0;
    }
    if(dp[u][num]!=-1){
        return dp[u][num];
    }
    for(auto v:g[u]){
        if(v==fa){
            continue;
        }
        dfs(v,u,1);
        dfs(v,u,2);
    }
    sort(g[u].begin(),g[u].end(),cmp);
    int sum=num;
    int res=0;
    for(auto v:g[u]){
        if(v==fa){
            continue;
        }
        if(sum&&dp[v][1]<1+dp[v][2]){
            sum--;
            res+=dp[v][1];
        }else{
            res+=dp[v][2]+1;
        }
    }
    dp[u][num]=res;
    //cout<<u<<" "<<num<<" "<<res<<endl;
    return res;
}
int now;
void solve(int u,int fa,int num,int z){
    if(g[u].size()==1){
        if(num==2){
            ans2[z].push_back(u);
        }
        ans2[z].push_back(u);
        return;
    }
    int sum=num;
    for(auto v:g[u]){
        if(v==fa){
            continue;
        }
        if(sum&&dp[v][1]<1+dp[v][2]){
            sum--;
            solve(v,u,1,z);
        }else{
            ans1.push_back(P(u,v));
            solve(v,u,2,++now);
        }
    }
    if(sum>0){
        ans2[z].push_back(u);
        if(num==2&&sum==2){
            ans2[z].push_back(u);
        }
    }
}
int main(){
    int t,n,u,v;
    cin>>t;
    while(t--){
        now=0;
        scanf("%d",&n);
        for(int i=1;i<=n;++i){
            //vis[i]=0;
            dp[i][0]=dp[i][1]=dp[i][2]=-1;
        }
        for(int i=1;i<n;++i){
            scanf("%d%d",&u,&v);
            g[u].push_back(v);
            g[v].push_back(u);
        }
        root=-1;
        for(int i=1;i<=n;++i){
            if(g[i].size()>2){
                root=i;
                break;
            }
        }
        if(root==-1){
            cout<<0<<endl;
            for(int i=0;i<=max(n,now);++i){
                g[i].clear();
                ans2[i].clear();
            }
            ans1.clear();
            continue;
        }
        int tot=dfs(root,-1,2);
        solve(root,-1,2,0);
        printf("%d\n",now);
        for(int i=0;i<now;++i){
            //cout<<ans2[i].size()<<" "<<ans2[i+1].size()<<endl;
            printf("%d %d %d %d\n",ans1[i].first,ans1[i].second,ans2[i][1],ans2[i+1][0]);
        }
        for(int i=0;i<=max(n,now);++i){
            g[i].clear();
            ans2[i].clear();
        }
        ans1.clear();
    }
    return 0;
}