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 JAVA):

Solution:
//https://codeforces.com/contest/1521/problem/D
//D. Nastia Plays with a Tree
import java.util.*;
import java.io.*;
public class CF_1521_D{

	static ArrayList<ArrayList<Integer>> ans;

	static int dfs(int u, int parent, ArrayList<ArrayList<Integer>> al){
		int children = 0;
		int to = u;
		for(int v : al.get(u)){
			if(v==parent)
				continue;
			int x = dfs(v, u, al);
			if(x<0)
				continue;

			children++;

			if(children==1)
				to = x;
			else if(children==2){
				ArrayList<Integer> a = new ArrayList<Integer>();
				a.add(parent);
				a.add(u);
				a.add(to);
				a.add(x);
				ans.add(a);
				to = -1;
			}
			else{
				ArrayList<Integer> a = new ArrayList<Integer>();
				a.add(u);
				a.add(v);
				a.add(v);
				a.add(x);
				ans.add(a);
			}
		}
		return to;
	}

	public static void main(String[] args) throws Exception{
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st;

		int t = Integer.parseInt(br.readLine());

		while(t-->0){
			int n = Integer.parseInt(br.readLine());

			ArrayList<ArrayList<Integer>> al = new ArrayList<ArrayList<Integer>>();
			for(int i=0;i<n;i++)
				al.add(new ArrayList<Integer>());

			for(int i=0;i<n-1;i++){
				st = new StringTokenizer(br.readLine().trim());
				int u = Integer.parseInt(st.nextToken())-1;
				int v = Integer.parseInt(st.nextToken())-1;
				al.get(u).add(v);
				al.get(v).add(u);
			}

			ans = new ArrayList<ArrayList<Integer>>();

			int root = 0;
			for(root=0;root<n;root++)
				if(al.get(root).size()==1)
					break;

			int to = dfs(root, -1, al);

			sb.append(ans.size()+"\n");
			for(int i=0;i<ans.size();i++){
				ArrayList<Integer> a = ans.get(i);
				sb.append(a.get(0)+1+" ").append(a.get(1)+1+" ").append(to+1+" ").append(a.get(2)+1+"\n");
				to = a.get(3);
			}
		}

		pw.print(sb);
		pw.flush();
		pw.close();
	}
}