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<iostream>
#include<iomanip>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cassert>
#include<ctime>
#include<cwctype>
#include<chrono>
#include<random>

#include<cstring>
#include<vector>
#include<queue>
#include<set>
#include<map>
#include<unordered_set>
#include<unordered_map>
#include<bitset>

#include<cmath>
#include<complex>

using namespace std;
#define szof(x) ((int) x.size())

vector<vector<int>> adj;
vector<vector<int>> c;
vector<pair<int,int>> edges, bamboo;
vector<int> vis, p, leaves;


void reset(int n){
	adj.resize(n+1);
	c.resize(n+1);
	for(int i = 0; i < n+1; ++i){
		adj[i].clear();
		c[i].clear();
	}
	edges.clear(), bamboo.clear();
	vis.clear(); vis.resize(n+1,0);
	p.clear(); p.resize(n+1,0);
	leaves.clear(); leaves.resize(n+1,0);
}

int dfs(int root, int par = 0){
	for(int cur : adj[root]){
		if(cur == par) continue;
		int ans = dfs(cur, root);
		if(ans) c[root].push_back(cur);
		
	}
	for(int i = 2; i < szof(c[root]); ++i){
		p[c[root][i]] = 0;
		edges.push_back({root,c[root][i]});
	}
	if(szof(c[root]) > 2) c[root].resize(2);
	if(szof(c[root]) == 2){
		if(par != 0) edges.push_back({root,par});
		p[root] = 0;
		return 0;
	}
	p[root] = par;
	return 1;
}

void dfs2(int root){
	if(vis[root]) return;
	vis[root] = 1;
	int sz = 0;
	for(int cur : c[root]) dfs2(cur), sz++;
	if(p[root]) dfs2(p[root]), sz++;
	if(sz == 1 || sz == 0) leaves.push_back(root);
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int T; cin >> T;
	for(int tt = 0; tt < T; ++tt){
		int n; cin >> n;
		reset(n);
		for(int i = 0; i < n-1; ++i){
			int a, b; cin >> a >> b;
			adj[a].push_back(b);
			adj[b].push_back(a);
		}
		dfs(1,0);
		for(int i = 1; i < n+1; ++i){
			if(vis[i]) continue;
			leaves.clear();
			dfs2(i);
			assert(szof(leaves) <= 2);
			if(szof(leaves) == 1) bamboo.push_back({leaves[0],leaves[0]});
			if(szof(leaves) == 2) bamboo.push_back({leaves[0], leaves[1]});
		}
		cerr << szof(edges) << " " << szof(bamboo) << endl;
		cout << szof(edges) << endl;
		for(int i = 0; i < szof(edges); ++i) cout << edges[i].first << " " << edges[i].second << " " << bamboo[i].second << " " << bamboo[i+1].first << endl;
	}
}