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 ar array
#define ll long long
typedef int uci;
#define int long long
#define F first
#define S second

const int MAX_N = 1e5 + 1;
const int MOD = 1e9 + 7;
const int INF = 1e9;
const ll LINF = 1e18;

//! function insert

//THINK FIRST, CODE SECOND
//DON'T GET STUCK ON ONE STRATEGY
//REDUCE
int out{};
vector<ar<int, 4>> top;

pair<int, int> recurse(int v, int parent, vector<vector<int>> &adj){
	if(adj[v].size() == 1 && adj[v][0] == parent)
		return {v,v};
	vector<pair<pair<int,int>, int>> ends;
	int l = -1, r = -1;
	for(int i{}; i < adj[v].size(); ++i){
		if(adj[v][i] != parent){
			auto a = (recurse(adj[v][i], v, adj));
			if(a.first == adj[v][i]){
				if(l == -1){
					l = a.second;
				}else if(r == -1){
					r = a.second;
				}else{
					ends.push_back({a, adj[v][i]});
				}
			}else if(a.second == adj[v][i]){
				if(l == -1){
					l = a.first;
				}else if(r == -1){
					r = a.first;
				}else{
					ends.push_back({a, adj[v][i]});
				}
			}else{
				ends.push_back({a, adj[v][i]});
			}
		}
	}
	if(l == -1)
		l = v;
	if(r == -1)
		r = v;
	for(int i{}; i < ends.size(); ++i){
		out++;
		top.push_back({v,ends[i].second, l, ends[i].first.second});
		l = ends[i].first.first;
	}
	return {l, r};
}

void solve() {
	out = 0;
	top.clear();
	int n;
	cin >> n;
	vector<vector<int>> adj(n+1);
	for(int i{}; i < n-1; ++i){
		int a, b;
		cin >> a >> b;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}

	recurse(1, 0, adj);
	cout << out << '\n';
	for(int i{}; i < top.size(); ++i){
		cout << top[i][0] << ' ' << top[i][1] << ' ' << top[i][2] << ' ' << top[i][3] << '\n';
	}
}

uci main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);

    int tc; cin >> tc;
    for (int t = 1; t <= tc; t++) {
        // cout << "Case #" << t  << ": ";
        solve();
    }
}