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;

class union_find {
  public:
	vector<int> arr;
	union_find(int n) {
		arr.resize(n);
		fill(arr.begin(), arr.end(), -1);
	}
	int find(int x) { return arr[x] < 0 ? x : arr[x] = find(arr[x]); }
	void unite(int x, int y) {
		x = find(x), y = find(y);
		if (x == y) return;
		if (arr[x] > arr[y]) swap(x, y);
		arr[x] += arr[y];
		arr[y] = x;
	}
	bool connected(int x, int y) { return find(x) == find(y); }
	int size(int x) { return -arr[find(x)]; }
};
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int tc;
	cin >> tc;
	while (tc--) {
		int n;
		cin >> n;
		vector<vector<int>> ad(n);
		vector<pair<int, int>> ed;
		for (int i = 1; i < n; i++) {
			int a, b;
			cin >> a >> b;
			a--, b--;
			ad[a].push_back(b);
			ad[b].push_back(a);
			ed.push_back({a, b});
		}
		if (n == 2) {
			cout << 0 << "\n";
			continue;
		}
		int root = 0;
		for (int i = 0; i < n; i++) {
			if ((int)ad[i].size() > 1) {
				root = i;
			}
		}
		vector<int> dp1(n), chs(n);
		vector<bool> used(n);
		set<pair<int, int>> st;
		function<void(int, int)> dfs1 = [&](int cur, int par) {
			bool bo = true;
			int m0 = -1, m1 = -1;
			for (int ch : ad[cur]) {
				if (ch == par) continue;

				dfs1(ch, cur);
				if (used[ch]) continue;
				bo = false;
				chs[cur] += chs[ch];
				if (m0 == -1) {
					m0 = ch;
				} else if (dp1[ch] == dp1[m0]) {
					m1 = m0;
					m0 = ch;
				} else if (dp1[ch] > dp1[m0]) {
					m1 = m0;
					m0 = ch;
				} else if (m1 == -1) {
					m1 = ch;
				} else if (dp1[ch] > dp1[m1]) {
					m1 = ch;
				}
			}

			if (m1 != -1) {
				used[cur] = true;
				st.insert({cur, m0});
				st.insert({m0, cur});
				st.insert({cur, m1});
				st.insert({m1, cur});
				dp1[cur] = 0;
			} else if (m0 != -1) {
				st.insert({cur, m0});
				st.insert({m0, cur});
			}
			if (bo) {
				chs[cur] = 1;
				dp1[cur] = 1;
			}
		};
		dfs1(root, -1);

		vector<pair<int, int>> elim;
		union_find uf(n);
		vector<vector<int>> ad2(n);
		for (int i = 0; i < (int)ed.size(); i++) {
			int a = ed[i].first;
			int b = ed[i].second;
			if (st.find({a, b}) != st.end()) {
				uf.unite(a, b);
				ad2[a].push_back(b);
				ad2[b].push_back(a);
				continue;
			}
			elim.push_back({a, b});
		}
		vector<pair<int, int>> ne;
		int ind = -1;
		vector<pair<int, int>> tt0;
		for (int i = 0; i < n; i++) {
			if ((int)ad2[i].size() > 1) continue;
			if ((int)ad2[i].size() == 0) {
				tt0.push_back({uf.find(i), i});
				tt0.push_back({uf.find(i), i});
			} else {
				tt0.push_back({uf.find(i), i});
			}
		}
		sort(tt0.begin(), tt0.end());
		map<int, int> mp;
		for (int i = 0; i < tt0.size(); i += 2) {
			int a = tt0[i].second, b = tt0[i + 1].second;
			mp[a] = b;
			mp[b] = a;
		}
		for (int i = 0; i < n; i++) {
			if ((int)ad2[i].size() > 1) continue;
			ind = i;
			break;
		}
		for (int i = 0; i < n; i++) {
			if (i == ind) continue;
			if ((int)ad2[i].size() > 1) continue;
			if (uf.connected(ind, i)) continue;
			ne.push_back({ind, i});
			uf.unite(ind, i);
			int a0 = mp[ind];
			int b0 = mp[i];
			mp[a0] = b0;
			mp[b0] = a0;
			ind = a0;
		}
		cout << elim.size() << "\n";
		for (int i = 0; i < (int)elim.size(); i++) {
			cout << elim[i].first + 1 << " " << elim[i].second + 1 << " "
			     << ne[i].first + 1 << " " << ne[i].second + 1 << "\n";
		}
	}
	return 0;
}