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 <algorithm>    // std::sort
#include <iostream>
#include <string>		// to_string
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <queue> 
using namespace std;

void solve() {
	// string:
	//char** vals = new char* [n];
	//for (int i = 0; i < n; i++) {
	//	string str = "";
	//	cin >> str;
	//	vals[i] = new char[n];
	//	for (int j = 0; j < n; j++) {
	//		vals[i][j] = str[j];
	//	}
	//}
	int n;
	cin >> n;
	unordered_map<int, unordered_set<int>> G;
	vector<int> remove;
	vector<int> add;
	int* deg = new int[n + 1];
	for (int i = 0; i <= n; i++) {
		deg[i] = 0;
	}
	int count = 0;
	for (int i = 0; i < n - 1; i++) {
		int a, b;
		cin >> a;
		cin >> b;
		deg[a]++;
		deg[b]++;
		if (G.find(a) == G.end()) {
			unordered_set<int> temp;
			G.insert({ a, temp });
		}
		if (G.find(b) == G.end()) {
			unordered_set<int> temp;
			G.insert({ b, temp });
		}
		G.find(a)->second.insert(b);
		G.find(b)->second.insert(a);

	}
	unordered_map<int, unordered_set<int>> Gnew;
	int* degNew = new int[n + 1];
	queue<int> leavesNew;
	for (int i = 1; i <= n; i++) {
		degNew[i] = 0;
		if (deg[i] >= 3) {
			if (Gnew.find(i) == Gnew.end()) {
				unordered_set<int> temp;
				Gnew.insert({ i, temp });
			}
			unordered_set<int> vertices = G.find(i)->second;
			for (unordered_set<int>::iterator itr = vertices.begin(); itr != vertices.end(); itr++) {
				if (deg[*itr] >= 3) {
					Gnew.find(i)->second.insert(*itr);
					degNew[i]++;
				}
			}
			if (degNew[i] == 1) {

				leavesNew.push(i);
			}
		}
	}
	while (!leavesNew.size() == 0) {
		int next = leavesNew.front();
		leavesNew.pop();
		if (Gnew.find(next)->second.size() != 1 || deg[next] < 3) {
			continue;
		}
		count++;
		unordered_set<int> vertices = Gnew.find(next)->second;
		unordered_set<int>::iterator itr = vertices.begin();
		// cout << next << "\n";
		while (Gnew.find(*itr)->second.size() == 0 || deg[*itr] < 3) {
			itr++;
			if (itr == vertices.end()) {
				break;
			}
		}
		// cout << "REMOVING: " << *itr << ", " << next << " \n";
		remove.push_back(*itr);
		remove.push_back(next);
		deg[*itr]--;
		deg[next]--;
		
		G.find(*itr)->second.erase(next);
		G.find(next)->second.erase(*itr);
		if (Gnew.find(*itr)->second.size() == 1 || deg[*itr] == 2) {
			unordered_set<int> itrNeighbors = Gnew.find(*itr)->second;
			for (unordered_set<int>::iterator itr2 = itrNeighbors.begin(); itr2 != itrNeighbors.end(); itr2++) {
				Gnew.find(*itr2)->second.erase(*itr);
				// cout << ":: " << *itr2 << " " << *itr << "\n";
				if (Gnew.find(*itr2)->second.size() == 1 && deg[*itr2] >= 3) {
					leavesNew.push(*itr2);
				}
			}
		}
		if (Gnew.find(*itr)->second.size() == 2 && deg[*itr] >= 3) {
			leavesNew.push(*itr);
		}
		Gnew.find(next)->second.erase(*itr);
		Gnew.find(*itr)->second.erase(next);
		
	}
	for (int i = 1; i <= n; i++) {
		while (deg[i] >= 3) {
			count++;
			unordered_set<int>::iterator begin = G.find(i)->second.begin();
			remove.push_back(*begin);
			remove.push_back(i);
			deg[i]--;
			deg[*begin]--;
			G.find(*begin)->second.erase(i);
			G.find(i)->second.erase(*begin);

		}
	}
	cout << count << "\n";
	// find leaves
	unordered_set<int> leaves;
	unordered_map<int, int> leavesMap;
	for (int i = 1; i <= n; i++) {
		deg[i] = G.find(i)->second.size();
		if (deg[i] <= 1) {
			leaves.insert(i);
			if (deg[i] == 0) {
				leavesMap.insert({ i, i });
				// cout << i << " has no neighbors\n";
			}
		}
	}
	for (unordered_set<int>::iterator itr = leaves.begin(); itr != leaves.end(); itr++) {
		if (deg[*itr] == 0) {
			continue;
		}
		int cur = *itr;
		int next = 0;
		while (true) {
			unordered_set<int> vertices = G.find(cur)->second;
			unordered_set<int>::iterator i = vertices.begin();
			if (*i == next) {
				i++;
			}
			next = *i;
			if (deg[next] == 1) {
				break;
			}
			else {
				int temp = cur;
				cur = next;
				next = temp;
			}
		}
		leavesMap.insert({ *itr, next });
		// cout << *itr << ": " << next << "\n";
	}

	for (int i = 0; i < count; i++) {
		unordered_set<int>::iterator itr = leaves.begin();
		int start = *itr;
		itr++;
		if (*itr == leavesMap.find(start)->second) {
			itr++;
		}
		int next = *itr;
		add.push_back(start);
		add.push_back(next);
		deg[start]++;
		deg[next]++;
		// cout << "SN: " << start << " " << next << "\n";
		int t1 = leavesMap.find(start)->second;
		int t2 = leavesMap.find(next)->second;
		// cout << "THE T's: " << t1 << " " << t2 << "\n";
		if (deg[start] != 1) {
			leaves.erase(start);
		}
		leavesMap.find(t1)->second = t2;
		if (deg[next] != 1) {
			leaves.erase(next);
		}
		leavesMap.find(t2)->second = t1;
	}
	for (int i = 0; i < count; i++) {
		cout << remove.at(2 * i) << " " << remove.at(2 * i + 1) << " " << add.at(2 * i) << " " << add.at(2 * i + 1) << "\n";
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int t;
	cin >> t;
	while (t--) {
		solve();
	}
}