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
using namespace std;
const int maxn = 500500;
int dp[maxn][2], d[maxn];
vector<int> g[maxn];
vector<pair<int,int>> edge, path;
pair<int,int> c[maxn];
void dfs(int u,int p) {
	int sum = 0;
	int child = 0;
	for(int to : g[u]) {
		if(to == p) continue;
		dfs(to, u);
		sum += dp[to][0];
		child++;
	}
	if(!child) {
		dp[u][1] = 0;
		dp[u][0] = 1;
		c[u] = {-1, -1};
		d[u] = -1;
		return;
	}
	int who = -1;
	for(int to : g[u]) {
		if(to == p) continue;
		if(dp[u][1] > dp[to][1] + sum - dp[to][0]) {
			who = to;
			dp[u][1] = dp[to][1] + sum - dp[to][0];
		}
	}
	d[u] = who;
	vector<pair<int,int>> f;
	for(int to : g[u]) {
		if(to == p) continue;
		f.push_back({dp[to][1] - dp[to][0], to});
	}
	sort(f.begin(),f.end());
	if(f.size() > 1) {
		dp[u][0] = sum + f[0].first + f[1].first + (u != 1);
		c[u] = {f[0].second, f[1].second};
	}
	if(dp[u][0] > sum + f[0].first + (u != 1)) {
		dp[u][0] = sum + f[0].first + (u != 1);
		for(int to : g[u]) {
			if(to == p) continue;
			c[u] = {to, -1};
			break;
		}
	}
}
int res(int u,int p = -1,int ok = 0) {
	if(!ok) {
		if(p != -1) {
			edge.push_back({u, p});
		}
		int child = 0;
		for(int to : g[u]) {
			if(to == p) continue;
			child++;
		}
		if(!child) {
			path.push_back({u, u});
			return -1;
		}
		if(c[u].second == -1) {
			int l = res(c[u].first, u, 1);
			path.push_back({u, l});
			for(int to : g[u]) {
				if(to != p && to != c[u].first) {
					res(to, u, 0);
				}
			}
		} else {
			int l = res(c[u].first, u, 1);
			int r = res(c[u].second, u, 1);
			path.push_back({l, r});
			for(int to : g[u]) {
				if(to == p || to == c[u].first || to == c[u].second) continue;
				res(to, u, 0);
			}
		}
		return -1;
	} else {
		int child = 0;
		for(int to : g[u]) {
			if(to == p) continue;
			child++;
		}
		if(!child) return u;
		for(int to : g[u]) {
			if(to == p || to == d[u]) continue;
			res(to, u, 0);	
		}
		return res(d[u], u, 1);
	}
}
int main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	int t; cin >> t;
	while(t--) {
		int n; cin >> n;
		for(int i = 1; i <= n; i++) {
			g[i].clear();
			c[i] = {-1, -1};
			d[i] = -1;
			for(int j = 0; j < 2; j++) dp[i][j] = 2e9;
		}
		for(int i = 1; i < n; i++) {
			int u, v; cin >> u >> v; g[u].push_back(v); g[v].push_back(u);
		}
		dfs(1, -1);
		path.clear();
		edge.clear();
		res(1, -1);
		int it = 0;
		assert(path.size() - 1 == edge.size());
		vector<pair<pair<int,int>, pair<int,int>>> ans;
		int u = path[0].first;
		for(int i = 1; i < path.size(); i++) {
			ans.push_back({edge[it], {u, path[i].first}});
			it++;
			u = path[i].second;
		}
		cout << ans.size() << "\n";
		for(auto x : ans) {
			cout << x.first.first << " " << x.first.second << " ";
			cout << x.second.first << " " << x.second.second << "\n";
		}
	}
}