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:
#ifdef LOCAL
#pragma warning(disable:4996)
#pragma warning(disable:4244)
#pragma warning(disable:4554)
#define gets gets_s

#endif
#include<map>
#include<set>
#include<list>
#include<cmath>
#include<stack>
#include<queue>
#include<cmath>
#include<vector>
#include<string>
#include<cctype>
#include<cstdio>
#include<bitset>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<iomanip>
#include<assert.h>
#define ll long long
#define cl(a,x) memset((a),(x),sizeof(a))
#define lson 2*i
#define rson 2*i+1
#define sf scanf
#define ull unsigned long long
#define lowbit(x) (x)&(-x)
#define pii pair<int,int>
#define pll pair<long long,long long>
#define pdd pair<double,double>
#define ti tree[i]
#define endl "\n"
#define debug(num) #num << "=" << num << " "
ll q_pow(ll x, ll n, ll mod) { ll ret = 1; while (n) { if (n & 1) ret = x * ret%mod; x = x * x%mod; n >>= 1; }return ret; }
ll __gcd(ll x, ll y) { if (!y) return x; return __gcd(y, x%y); }
ll getbit(ll now) { int cnt = 0; while (now) { cnt++; now -= lowbit(now); }return cnt; }
int dx[] = { -1,1,0,0 };//上下左右
int dy[] = { 0,0,-1,1 };//
using namespace std;
const ll maxn = 1e5 + 10;
const ll INF = 0x3f3f3f3f;
const ll IINF = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9;
int mod = 998244353;
void add(ll &a, ll num) { a += num; if (a >= mod) a -= mod; }

vector<int> edge[maxn];
int head[maxn], tail[maxn];
int vis[maxn];
vector<pii> deledge, addedge;

void dfs(int pos, int fa) {
	for (auto to : edge[pos]) {
		if (to == fa) continue;
		dfs(to, pos);
		if (head[to] == to) {
			if (tail[pos] == pos) {
				tail[pos] = tail[to];
				vis[to] = 1;
			}
			else if (head[pos] == pos) {
				head[pos] = tail[to];
				vis[to] = 1;
			}
		}
	}

	for (auto to : edge[pos]) {
		if (vis[to] == 1) continue;
		if (to == fa) continue;
		deledge.emplace_back(make_pair(to, pos));
		addedge.emplace_back(make_pair(tail[pos], head[to]));
		tail[pos] = tail[to];
	}
}

void solve() {
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		head[i] = tail[i] = i;
		edge[i].clear();
		vis[i] = 0;
	}
	deledge.clear(); addedge.clear();

	int u, v;
	for (int i = 1; i < n; i++) {
		cin >> u >> v;
		edge[u].emplace_back(v);
		edge[v].emplace_back(u);
	}

	dfs(1, 0);
	cout << deledge.size() << endl;
	for (int i = 0; i < deledge.size(); i++) {
		cout << deledge[i].first << " " << deledge[i].second << " " << addedge[i].first << " " << addedge[i].second << endl;
	}
}

signed main(int argc, char *argv[]) {
	if (argc == 2 && strcmp("-debug", argv[1]) == 0) {
		freopen("in.txt", "r", stdin);
		freopen("out.txt", "w", stdout);
	}

	cout << fixed << setprecision(20); ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int t = 1;
	cin >> t;

	while (t--) {
		solve();
	}

	return 0;
}