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:
// Problem: D. Nastia Plays with a Tree
// Contest: Codeforces - Codeforces Round #720 (Div. 2)
// URL: https://codeforces.com/contest/1521/problem/D
// Memory Limit: 256 MB
// Time Limit: 3000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
inline int read(){
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
   return s*w;
}
bool Vis[1000003],f[1000003];
vector<int> e[1000003],ee[1000003];
#define pb push_back
int d[1000003];
int C,U1[1000003],V1[1000003],U2[1000003],V2[1000003];
int CC;
int FIR,LST;
void dfs(int x,int fa)
{
	for(int y:e[x]) if(y!=fa) dfs(y,x);
	int A=0,B=0;
	for(int y:e[x]) if(y!=fa)
	{
		if(!f[y]) 
		{
			if(!A) A=y; 
			else if(!B) B=y;
			else
			{
				U1[++CC]=x,V1[CC]=y;
			}
		}
		else U1[++CC]=x,V1[CC]=y;
	}
	if(A&&B)
	{
		f[x]=1;
		ee[A].pb(x);
		ee[x].pb(A);
		ee[B].pb(x);
		ee[x].pb(B);
		// printf("* %d %d %d\n",A,x,B);
	}
	else if(A)
	{
		ee[A].pb(x);
		ee[x].pb(A);
		// printf("* %d %d\n",x,A);
	}
	return ;
}
void dfs2(int x)
{
	Vis[x]=1,LST=x;
	for(int y:ee[x]) if(!Vis[y]) dfs2(y);
}
void print()
{
	printf("%d\n",C);
	for(int i=1; i<=C; ++i) 
	printf("%d %d %d %d\n",U1[i],V1[i],U2[i],V2[i]);
	return;
}
signed main()
{
    for(int T=read();T--;)
    {
    	C=0;CC=0;
    	int L=0,R=0;
    	int n=read();
    	for(int i=1; i<=n; ++i) e[i].clear(),ee[i].clear();
    	for(int i=1; i<=n; ++i) d[i]=0,Vis[i]=0,f[i]=0;
    	for(int i=1,u,v; i<n; ++i)
    	{
    		u=read(),v=read();
    		e[u].pb(v);e[v].pb(u);
    		++d[u],++d[v];
    	}
    	int rt=1;
    	for(int i=2; i<=n; ++i) if(d[i]>d[rt]) rt=i;
    	
    	// printf("#%d\n",rt);
    	dfs(rt,rt);
    	
    	for(int i=1; i<=n; ++i) if(!Vis[i]&&ee[i].size()<=1)
    	{
    		FIR=i;
    		dfs2(i);
    		// printf("%d %d\n",FIR,LST);
    		if(!L)
    		{
    			L=FIR,R=LST;
    		}
    		else
    		{
    			U2[++C]=R,V2[C]=FIR,R=LST;
    		}
    	}
    	//assert(C==CC);
    	print();
    }
	return 0;
}