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:
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.PriorityQueue;
import java.util.Random;
import java.util.StringTokenizer;
import java.util.TreeMap;
import java.util.TreeSet;

@SuppressWarnings("unused")
public class Solution{
	
	static ArrayList<int[]>[] g;
	static boolean[] dp;         //  dp[i] -- true is the parent edge of vertex i should be removed
	static boolean[] isDeleted;    // if the edge i is deleted
	static ArrayList<int[]> bamboo;    //  stores all the endpoints of all the bamboo components of forest
	static boolean[] visited;
	static ArrayList<Integer> leaves;
	static int ans = 0;
	
	
	public static void main(String[] args) throws IOException {
		FastScanner fs = new FastScanner();
    	PrintWriter out = new PrintWriter(System.out);
    	
    	int tt = fs.nextInt();
    	outer:
    	while(tt-->0) {
    		
    		ans = 0;
    		int n = fs.nextInt();
    		g = new ArrayList[n];
    		for(int i=0;i<n;i++) g[i] = new ArrayList<int[]>();
    		
    		dp = new boolean[n]; isDeleted = new boolean[n];
    		
    		for(int i=0;i<n-1;i++) {
    			int u = fs.nextInt()-1, v = fs.nextInt()-1;
    			g[u].add(new int[] {v, i});
    			g[v].add(new int[] {u, i});
    		}
    		
    		dfs(0, -1);
    		
    		visited = new boolean[n];
    		bamboo = new ArrayList<>();
    		leaves = new ArrayList<>();
    		for(int i=0;i<n;i++) {
    			if(!visited[i]) {
    				dfs2(i, i);
    				if(leaves.size()==2) {
    					bamboo.add(new int[] {leaves.get(0), leaves.get(1)});
    				}
    				else {
    					bamboo.add(new int[] {leaves.get(0), leaves.get(0)});
    				}
    				leaves.clear();
    			}
    		}
    		
    		ArrayList<int[]> deleted = new ArrayList<>(), added = new ArrayList<>();
    		
    		for(int v=0;v<n;v++) {
    			for(int[] e: g[v]) {
    				if(isDeleted[e[1]] && v<e[0])
    					deleted.add(new int[] {v, e[0]});
    			}
    		}
    		
    		for(int i=0;i<bamboo.size()-1;i++) added.add(new int[] {bamboo.get(i)[1], bamboo.get(i+1)[0]});
    		
    		out.println(ans);
    		
    		for(int i=0;i<deleted.size();i++) {
    			out.println((deleted.get(i)[0]+1) + " "+ (deleted.get(i)[1]+1) + " " + (added.get(i)[0]+1) + " " + (added.get(i)[1] + 1));
    		}
    		
    		
    	}
    	
    	out.close();
    }
	
	
	
	static void dfs(int v, int p) {
		int sz = g[v].size() - (p!=-1?1:0);
		for(int[] e: g[v]) {
			if(e[0]==p) continue;
			dfs(e[0], v);
			if(dp[e[0]]) {
				sz--; ans++;
				isDeleted[e[1]] = true;
			}
		}
		
		if(sz>=2) {
			dp[v] = true;
			for(int[] e: g[v]) {
				if(e[0]==p) continue;
				if(sz<=2) break;
				if(!dp[e[0]]) {
					sz--; ans++;
					isDeleted[e[1]] = true;
				}
			}
		}
	}
	
	
	static void dfs2(int v, int root) {
		visited[v] = true;
		int num = 0;
		for(int[] e: g[v]) {
			if(visited[e[0]] || isDeleted[e[1]]) continue;
			num++; dfs2(e[0], root);
		}
		if(v==root && num==1) {
			leaves.add(v);
		}
		else if(num==0) {
			leaves.add(v);
		}
	}
	
	

	
    static final Random random=new Random();
    
    static <T> void shuffle(T[] arr) {
    	int n = arr.length;
    	for(int i=0;i<n;i++	) {
    		int k = random.nextInt(n);
    		T temp = arr[k]; arr[k] = arr[i]; arr[i] = temp;
    	}
    }
    
    	
    static void ruffleSort(int[] a) {
    	int n=a.length;//shuffle, then sort 
    	for (int i=0; i<n; i++) {
    		int oi=random.nextInt(n); int temp=a[oi];
    		a[oi]=a[i]; a[i]=temp;
    	}
    	Arrays.sort(a);
    }
    
    static void ruffleSort(long[] a) {
    	int n=a.length;//shuffle, then sort 
    	for (int i=0; i<n; i++) {
    		int oi=random.nextInt(n); long temp=a[oi];
    		a[oi]=a[i]; a[i]=temp;
    	}
    	Arrays.sort(a);
    }
   
  
    
    static void reverse(int[] arr, int l, int r) {
    	for(int i=l;i<l+(r-l)/2;i++){
    		int temp = arr[i]; arr[i] = arr[r-i+l-1]; arr[r-i+l-1] = temp;
    	}
    }
    
    static void reverse(long[] arr, int l, int r) {
    	for(int i=l;i<l+(r-l)/2;i++){
    		long temp = arr[i]; arr[i] = arr[r-i+l-1]; arr[r-i+l-1] = temp;
    	}
    }
    
    
    static <T> void reverse(T[] arr, int l, int r) {
    	for(int i=l;i<l+(r-l)/2;i++) {
    		T temp = arr[i]; arr[i] = arr[r-i+l-1]; arr[r-i+l-1] = temp;
    	}
    }
    	
    	
    static class FastScanner{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer("");
     
    	public String next(){
    		while(!st.hasMoreElements()){
    			try{
    				st = new StringTokenizer(br.readLine());
    			} catch(IOException e){
    				e.printStackTrace();
    			}
    		}
    		return st.nextToken();
    	}
    		
    	public String nextLine() throws IOException {
    		return br.readLine();
    	}
    		
    	public int nextInt(){
    		return Integer.parseInt(next());
    	}
     
    	public int[] readArray(int n){
    		int[] a = new int[n];
    		for(int i=0;i<n;i++)
    			a[i] = nextInt();
    		return a;
    	}
    		
    	public long nextLong() {
    		return Long.parseLong(next());
    	}
    		
    	public char nextChar() {
    		return next().toCharArray()[0];
    	}
    }
   	
}