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>
#define ll long long
#define ull unsigned long long
#define ld long double
#define pii pair <int, int>
#define pll pair <ll, ll>
#define pci pair <char, int>
#define pld pair <ld, ld>
#define ppld pair <pld, pld>
#define ppll pair <pll, pll>
#define pldl pair <ld, ll>
#define vll vector <ll>
#define vvll vector <vll>
#define vpll vector <pll>
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define mll map <ll, ll>
#define fastmap gp_hash_table
#define cd complex <double>
#define vcd vector <cd>
#define PI 3.14159265358979
#pragma 03
using namespace std;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
vpll added_edges, deleted_edges;
vll adj[200005], radj[200005];
bool use_par[200005];
ll par[200005];
bool used[200005];
bool custom_comp(ll u, ll v){
	return adj[u].size() < adj[v].size();
}
pll dfs(ll u, ll p){
	par[u] = p;
	pll cur = mp(u, u); 
	vpll goes;
	for (auto v : adj[u]){
		if (v == p) continue;
		radj[u].eb(v);
		pll go = dfs(v, u);
		goes.eb(go);
	}
	for (ll i = 0; i < (ll) goes.size(); i++) used[i] = 1;
	for (ll i = 0; i < (ll) goes.size(); i++){
		pll go = goes[i];
		if ((cur.fi == u) && (go.fi == radj[u][i])) cur.fi = go.se;
		else if ((cur.fi == u) && (go.se == radj[u][i])) cur.fi = go.fi;
		else if ((cur.se == u) && (go.fi == radj[u][i])) cur.se = go.se;
		else if ((cur.se == u) && (go.se == radj[u][i])) cur.se = go.fi;
		else used[i] = 0;
	}
	for (ll i = 0; i < (ll) goes.size(); i++){
		if (used[i]) continue;
		pll go = goes[i];
		use_par[radj[u][i]] = 0;
		added_edges.eb(cur.fi, go.fi);
		cur.fi = go.se;
	}
	return cur;
}
void solve(){
	ll n; cin >> n;
	added_edges.clear(); deleted_edges.clear();
	for (ll i = 1; i <= n; i++){
		adj[i].clear(); use_par[i] = 1; radj[i].clear();
	}
	for (ll i = 1; i < n; i++){
		ll u, v; cin >> u >> v;
		adj[u].eb(v); adj[v].eb(u);
	}
	for (ll i = 1; i <= n; i++) sort(adj[i].begin(), adj[i].end(), custom_comp);
	dfs(1, -1);
	for (ll i = 1; i <= n; i++){
		if ((par[i] != -1) && (use_par[i] == 0)) deleted_edges.eb(i, par[i]);
	}
	assert(deleted_edges.size() == added_edges.size());
	cout << (ll) added_edges.size() << "\n";
	for (ll i = 0; i < (ll) added_edges.size(); i++){
		cout << deleted_edges[i].fi << " " << deleted_edges[i].se << " " << added_edges[i].fi << " " << added_edges[i].se << "\n";
	}
}
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	ll t; cin >> t;
	while (t--) solve();
}