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 pb push_back
#define mp make_pair
#define fir first
#define sec second
using namespace std;
vector<pair<pair<int, int>, pair<int, int>>> ans;
const int N = 1e5 + 5;
int n, fa[N], f[N][2], g[N][2];
bool vis[N]; 
vector<pair<int, bool>> G[N];
vector<pair<int, int>> ban, tmp, vert;
pair<int, int> cur;
void Solve(int u) {
	if(u != 1 && G[u].size() == 1) {
		f[u][0] = f[u][1] = 0;
		return;
	}
	int res = 0;
	for(pair<int, int> e : G[u]) {
		int v = e.fir;
		if(v == fa[u]) {
			continue;
		}
		fa[v] = u;
		Solve(v);
		res += f[v][0] + 1;
	}
	tmp.clear();
	for(pair<int, int> e : G[u]) {
		int v = e.fir;
		if(v == fa[u]) {
			continue;
		}
		tmp.pb(mp(f[v][1] - (f[v][0] + 1), v));
	}
	sort(tmp.begin(), tmp.end());
	f[u][1] = res;
	g[u][0] = 0;
	if(f[u][1] + tmp[0].fir < f[u][1]) {
		f[u][1] += tmp[0].fir;
		g[u][0] = tmp[0].sec;
	}
	f[u][0] = f[u][1];
	g[u][1] = 0;
	if(tmp.size() >= 2 && f[u][0] + tmp[1].fir < f[u][0]) {
		f[u][0] += tmp[1].fir;
		g[u][1] = tmp[1].sec;
	}
}
void Get(int u, int type) {
	if(u != 1 && G[u].size() == 1) {
		return;
	}
	if(type == 0) {
		if(g[u][0]) {
			Get(g[u][0], 1);
		}
		if(g[u][1]) {
			Get(g[u][1], 1);
		}
		for(pair<int, bool> &e : G[u]) {
			int v = e.fir;
			if(v == fa[u] || v == g[u][0] || v == g[u][1]) {
				continue;
			}
			e.sec = true;
			ban.pb(mp(u, v));
			Get(v, 0);
		}
	} else {
		if(g[u][0]) {
			Get(g[u][0], 1);
		}
		for(pair<int, bool> &e : G[u]) {
			int v = e.fir;
			if(v == fa[u] || v == g[u][0]) {
				continue;
			}
			e.sec = true;
			ban.pb(mp(u, v));
			Get(v, 0);
		}
	}
} 
void Block(int u, int rt) {
	vis[u] = true;
	int nxt = 0;
	for(pair<int, int> e : G[u]) {
		int v = e.fir;
		if(v == fa[u] || e.sec) {
			continue;
		}
		nxt++;
		Block(v, rt);
	}
	if(!nxt) {
		if(cur.fir) {
			cur.sec = u;
		} else {
			cur.fir = u;
		}
	}
	if(u == rt) {
		if(!cur.fir) {
			cur.fir = rt;
		}
		if(!cur.sec) {
			cur.sec = rt;
		}
	}
}
void Dfs(int u) {
	if(!vis[u]) {
		cur.fir = cur.sec = 0;
		Block(u, u);
		vert.pb(cur);
	}
	for(pair<int, int> e : G[u]) {
		int v = e.fir;
		if(v == fa[u]) {
			continue;
		}
		Dfs(v);
	}
}
int main() {
	ios::sync_with_stdio(false);
	int test;
	cin >> test;
	while(test--) {
		cin >> n;
		for(int i = 1; i <= n; i++) {
			G[i].clear();
			vis[i] = false;
		}
		ban.clear();
		vert.clear();
		for(int i = 1; i < n; i++) {
			int u, v;
			cin >> u >> v;
			G[u].pb(mp(v, false));
			G[v].pb(mp(u, false));
		}
		fa[1] = 0;
		Solve(1);
		Get(1, 0);
		Dfs(1);
		cout << f[1][0] << endl;
		for(int i = 0; i < f[1][0]; i++) {
			cout << ban[i].fir << ' ' << ban[i].sec << ' ' << vert[i].sec << ' ' << vert[i + 1].fir << endl; 
		}
	}
	return 0;
}