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 lo long long int 
#define PII pair<lo, lo>

template<typename T>
istream& operator>>(istream& in, vector<T>&v)
{
    for(lo i = 0; i < v.size(); i++)cin >> v[i];
    return in;
}

lo deleteEdges(vector<vector<lo>>&adj, lo parent, lo start, map<PII, bool>&toDelete, vector<lo>&nodes, vector<vector<lo>>&edges)
{
    int cnt = 0;
    
    for(int i = 0; i < adj[start].size(); i++)
    {
        if(adj[start][i] == parent)continue;
        lo x = deleteEdges(adj, start, adj[start][i], toDelete, nodes, edges);
        
        if(x == 0 || cnt + x > 2) {
            toDelete[{start, adj[start][i]}] = true;
            toDelete[{adj[start][i], start}] = true;
            nodes.push_back(adj[start][i]);
            edges.push_back({start, adj[start][i]});
            
        }
            
        else cnt+=x;
            
    }
    
    return (cnt < 2);
}

void leafDFS(lo parent, lo start, vector<vector<lo>>&adj, vector<lo>&leaves)
{
  int cnt = 0;
  
  for(auto child : adj[start])
  {
      if(child == parent)continue;
      leafDFS(start, child, adj, leaves);
      cnt++;
  }
  
  if(cnt == 1 && parent == -1)leaves.push_back(start);
  
  if(cnt == 0)leaves.push_back(start);
}

void solve()
{
   lo N, x, y;
   
   cin >> N;
   
   vector<vector<lo>>adj(N+1), temp(N+1);
   
   for(int i = 0; i < N - 1; i++)
   {
       cin >> x >> y;
       
       adj[x].push_back(y);
       adj[y].push_back(x);
   }
   
   vector<vector<lo>>edges;
   
   vector<lo>nodes(1,1);
   
   map<PII, bool>toDelete;
   
   x = deleteEdges(adj, -1, 1, toDelete, nodes, edges);
   
   for(int i = 1; i <= N; i++)
   {
       for(int j = 0; j < adj[i].size(); j++)
       {
           if(!toDelete[{i, adj[i][j]}])
           {
               temp[i].push_back(adj[i][j]);
           }
       }
   }
   
   vector<vector<lo>>bomboo;  vector<lo>leaves;
   
   for(int i = 0; i < nodes.size(); i++)
   {
      leaves.clear();
       
       leafDFS(-1, nodes[i], temp, leaves);
       
       if(leaves.size() == 2)
       bomboo.push_back({leaves[0], leaves[1]});
       
       if(leaves.size() == 1)
       bomboo.push_back({leaves[0], leaves[0]});
       
   }
   
   cout << edges.size() << endl;
   
//   for(int i = 0; i < edges.size(); i++)
//   cout << edges[i][0] << " " << edges[i][1] << endl;
 
  for(int i = 0; i < bomboo.size() - 1; i++)
  {
      cout << edges[i][0] << " " << edges[i][1] << " " << bomboo[i][0] << " " << bomboo[i+1][1] << endl;
  }

}

int main() {
	
	lo T;
	cin >> T;
	
	while(T--)
	{
	    solve();
	}
	
	return 0;
}

// 3
// 1 3 38 3
// 1 14 3 14
// 1 5 14 5