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 int               long long
#define pb                push_back
#define ppb               pop_back
#define pf                push_front
#define ppf               pop_front
#define all(x)            (x).begin(),(x).end()
#define uniq(v)           (v).erase(unique(all(v)),(v).end())
#define sz(x)             (int)((x).size())
#define fr                first
#define sc                second
#define pii               pair<int,int>
#define vi                vector<int>
#define vii               vector<pii>
#define mi                map<int,int>
#define mii               map<pii,int>
#define rep(i,a,b)        for(int i=a;i<b;i++)
#define el                 '\n'
 

  vi v[100005];
   vi vis(100005);
   vector<pair<pii,pii>>pr;
   

  

  pii dfs(int x){
     vis[x]=1;
   
     int fl=0,sl=0;
      for(auto i:v[x]){
          if(!vis[i]){ 

               
              pii y=dfs(i);
              if(y.sc>0){
                  pr.pb({{x,i},{y.fr,y.sc}});
              }
                else{
                  if(fl==0){
                      fl=y.fr;
                  }
                  else if(sl==0){
                      sl=y.fr;
                  }
                  else{
                     pr.pb({{x,i},{y.fr,i}});
                  }
              }
  
          }
      } 
       if(fl==0){
        return {x,0};
       }


      if(sl>0){
        return {fl,sl};
      }
      else{
         return  {fl,0};
      }




      
  }
void solve()
{      
      int n;
      cin>>n;


       rep(i,0,n+2){
          vis[i]=0;
          v[i].clear();
       }
       pr.clear();

      rep(i,0,n-1){
          int x,y;
          cin>>x>>y;

          v[x].pb(y);
          v[y].pb(x);
      }  

     pii ok=dfs(1);

     int x1=ok.fr;
      cout<<sz(pr)<<el;
     for(auto i:pr){
        cout<<i.fr.fr<<' '<<i.fr.sc<<' '<<x1<<' '<<i.sc.fr<<el;
        x1=i.sc.sc;
     }
  
}

signed main()
{
   
     ios_base::sync_with_stdio(false);
     cin.tie(0); cout.tie(0);
 
   int t=1;
   cin>>t;

   while(t--) solve();
   return 0;
}