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;

namespace program {
	const int N = 100005;
	
	struct edge {
		int to, nxt;
		edge() {}
		edge(int to_, int nxt_): to(to_), nxt(nxt_) {}
	} e[N << 1];
	int hd[N], cnt, fir[N], end[N];
	vector<pair<int, int> > del, ins;
	
	void adde(int u, int v) {
		e[++cnt] = edge(v, hd[u]); hd[u] = cnt;
		e[++cnt] = edge(u, hd[v]); hd[v] = cnt;
	}
	bool dfs(int u, int fa) {
		vector<int> son1, son2;
		for(int i = hd[u]; i; i = e[i].nxt) {
			int v = e[i].to;
			if(v == fa) continue;
			if(dfs(v, u)) {
				son1.push_back(v);
			}
			else {
				son2.push_back(v);
			}
		}
		if(!son1.size()) {
			end[u] = u;
		}
		else if(son1.size() == 1) {
			end[u] = end[son1[0]];
		}
		else {
			end[u] = end[son1[0]];
			fir[u] = end[son1[1]];
			if(fa) del.push_back(make_pair(fa, u));
			for(int i = 2; i < son1.size(); ++i) {
				del.push_back(make_pair(u, son1[i]));
				ins.push_back(make_pair(end[u], son1[i]));
				end[u] = end[son1[i]];
			}
		}
		for(int i = 0; i < son2.size(); ++i) {
			ins.push_back(make_pair(end[u], fir[son2[i]]));
			end[u] = end[son2[i]];
		}
		return son1.size() <= 1;
	}
	int main() {
		int T;
		scanf("%d", &T);
		while(T--) {
			int n;
			scanf("%d", &n);
			cnt = 0;
			memset(hd + 1, 0, sizeof(int) * n);
			for(int i = 1; i < n; ++i) {
				int u, v;
				scanf("%d%d", &u, &v);
				adde(u, v);
			}
			del.clear();
			ins.clear();
			dfs(1, 0);
			printf("%d\n", del.size());
			for(int i = 0; i < del.size(); ++i) {
				printf("%d %d %d %d\n", del[i].first, del[i].second, ins[i].first, ins[i].second);
			}
		}
		return 0;
	}
}
int main() {
	return program::main();
}