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.*;
import java.util.*;

public class Main{
	static int[][]dp;
	static LinkedList<Integer>[]adj;
	static int dfs(int i,int removed,int p) {
		if(dp[removed][i]!=-1)return dp[removed][i];
		int[][]anss=new int[2][adj[i].size()-(p==-1?0:1)];
		if(anss[0].length==0)return dp[removed][i]=0;
		int sum1=0;
		int idx=0;
		for(int j:adj[i]) {
			if(j==p)continue;
			for(int r=0;r<2;r++) {
				anss[r][idx]=dfs(j, r, i)+r;				
			}
			sum1+=anss[1][idx++];
		}
		//choose only one child to remain unremoved and remove others
		int[]ifRemained=new int[anss[0].length];
		idx=0;
		for(int j:adj[i]) {
			if(j==p)continue;
			ifRemained[idx]=sum1-anss[1][idx]+anss[0][idx];
			idx++;
		}
		int[]minPref=new int[ifRemained.length],minSuff=new int[ifRemained.length];
		for(int j=0;j<minPref.length;j++) {
			minPref[j]=ifRemained[j];
			if(j>0) {
				minPref[j]=Math.min(minPref[j], minPref[j-1]);
			}
		}
		for(int j=minPref.length-1;j>=0;j--) {
			minSuff[j]=ifRemained[j];
			if(j+1<minPref.length) {
				minSuff[j]=Math.min(minSuff[j], minSuff[j+1]);
			}
		}
		int ans=minPref[minPref.length-1];
		if(removed==1 && minPref.length>1) {//edge with parent is removed
			//we can choose 2 children to remain unremoved
			for(int j=0;j<minPref.length;j++) {
				int curAns=anss[0][j];
				int otherOne=1000000000;
				if(j>0) {
					otherOne=Math.min(otherOne, minPref[j-1]);
				}
				if(j+1<minPref.length) {
					otherOne=Math.min(otherOne, minSuff[j+1]);
				}
				otherOne-=anss[1][j];
				curAns+=otherOne;
				ans=Math.min(ans, curAns);
			}
		}
		
		
		return dp[removed][i]=ans;
	}
	static LinkedList<int[]>edges;
	static int[] dfs2(int removed,int i,int p) {
		int opt=dfs(i, removed, p);
		if((adj[i].size()-(p==-1?0:1))==0)return new int[] {i,-1};
		int[][]anss=new int[2][adj[i].size()-(p==-1?0:1)];
		int sum1=0;
		int idx=0;
		for(int j:adj[i]) {
			if(j==p)continue;
			for(int r=0;r<2;r++) {
				anss[r][idx]=dfs(j, r, i)+r;				
			}
			sum1+=anss[1][idx++];
		}
		//choose only one child to remain unremoved and remove others
		int[]ifRemained=new int[anss[0].length];
		int[]children=new int[ifRemained.length];
		idx=0;
		for(int j:adj[i]) {
			if(j==p)continue;
			ifRemained[idx]=sum1-anss[1][idx]+anss[0][idx];
			children[idx]=j;
			idx++;
		}
		int[]minPref=new int[ifRemained.length],minSuff=new int[ifRemained.length];
		int[]minPrefi=new int[ifRemained.length],minSuffi=new int[ifRemained.length];
		for(int j=0;j<minPref.length;j++) {
			minPref[j]=ifRemained[j];
			minPrefi[j]=children[j];
			if(j>0) {
				minPref[j]=Math.min(minPref[j], minPref[j-1]);
				if(minPref[j]==minPref[j-1]) {
					minPrefi[j]=minPrefi[j-1];
				}
			}
		}
		for(int j=minPref.length-1;j>=0;j--) {
			minSuff[j]=ifRemained[j];
			minSuffi[j]=children[j];
			if(j+1<minPref.length) {
				minSuff[j]=Math.min(minSuff[j], minSuff[j+1]);
				if(minSuff[j]==minSuff[j+1]) {
					minSuffi[j]=minSuffi[j+1];
				}
			}
		}
		int ans=minPref[minPref.length-1];
		if(ans==opt) {
			int onlyRem=minPrefi[minPref.length-1];
			int roots[]=dfs2(0,onlyRem, i);
			int curRoot=roots[0],candRoot=roots[1];
			int scndRoot=candRoot;
			for(int j:adj[i]) {
				if(j==p || j==onlyRem)continue;
				int newroots[]=dfs2(1,j, i);
				int newRoot=newroots[0],newcandRoot=newroots[1];
//				System.out.println(i+" "+j+" "+curRoot);
				edges.add(new int[] {i+1,j+1,curRoot+1,newRoot+1});
				curRoot=j;
				if(newcandRoot!=-1) {
					curRoot=newcandRoot;
				}
			}
			return new int[] {curRoot,scndRoot};
		}
		if(removed==1 && minPref.length>1) {//edge with parent is removed
			//we can choose 2 children to remain unremoved
			for(int j=0;j<minPref.length;j++) {
				int curAns=anss[0][j];
				int rem1=children[j];
				int rem2=-1;
				int otherOne=1000000000;
				if(j>0) {
					otherOne=Math.min(otherOne, minPref[j-1]);
					rem2=minPrefi[j-1];
				}
				if(j+1<minPref.length) {
					otherOne=Math.min(otherOne, minSuff[j+1]);
					if(otherOne==minSuff[j+1]){
						rem2=minSuffi[j+1];
					}
				}
				otherOne-=anss[1][j];
				curAns+=otherOne;
				if(curAns==opt) {
					int scndroot=dfs2(0, rem1, i)[0];
					int curRoot=dfs2(0,rem2, i)[0];
					for(int o:adj[i]) {
						if(o==p || o==rem2 || o==rem1)continue;
//						System.out.println(i+" "+j+" "+curRoot);
						int[]roots=dfs2(1,o, i);
						int newRoot=roots[0];
						edges.add(new int[] {i+1,o+1,curRoot+1,newRoot+1});
						curRoot=o;
						if(roots[1]!=-1) {
							curRoot=roots[1];
						}
					}
					return new int[] {curRoot,scndroot};
				}
			}
		}
		
		return new int[] {i,-1};
	}
	
	static void main() throws Exception{
		int n=sc.nextInt();
		adj=new LinkedList[n];
		for(int i=0;i<n;i++)adj[i]=new LinkedList<Integer>();
		for(int i=0;i<n-1;i++) {
			int x=sc.nextInt()-1,y=sc.nextInt()-1;
			adj[x].add(y);
			adj[y].add(x);
		}
		dp=new int[2][n];
		for(int i=0;i<2;i++) {
			for(int j=0;j<n;j++){
				dp[i][j]=-1;
			}
		}
		edges=new LinkedList<int[]>();
		dfs2(1,0, -1);
		pw.println(edges.size());
		while(!edges.isEmpty()) {
			int[]cur=edges.poll();
			pw.println(cur[0]+" "+cur[1]+" "+cur[2]+" "+cur[3]);
		}
    }
    public static void main(String[] args) throws Exception{
    	sc=new MScanner(System.in);
    	pw = new PrintWriter(System.out);
        int tc=1;
        tc=sc.nextInt();
        for(int i=1;i<=tc;i++) {
//            pw.printf("Case #%d: ", i);
            main();
        }
        pw.flush();
    }
    static PrintWriter pw;
    static MScanner sc;
    static class MScanner {
        StringTokenizer st;
        BufferedReader br;
        public MScanner(InputStream system) {
            br = new BufferedReader(new InputStreamReader(system));
        }
     
        public MScanner(String file) throws Exception {
            br = new BufferedReader(new FileReader(file));
        }
     
        public String next() throws IOException {
            while (st == null || !st.hasMoreTokens())
                st = new StringTokenizer(br.readLine());
            return st.nextToken();
        }
        public int[] intArr(int n) throws IOException {
            int[]in=new int[n];for(int i=0;i<n;i++)in[i]=nextInt();
            return in;
        }
        public long[] longArr(int n) throws IOException {
            long[]in=new long[n];for(int i=0;i<n;i++)in[i]=nextLong();
            return in;
        }
        public int[] intSortedArr(int n) throws IOException {
            int[]in=new int[n];for(int i=0;i<n;i++)in[i]=nextInt();
            shuffle(in);
            Arrays.sort(in);
            return in;
        }
        public long[] longSortedArr(int n) throws IOException {
            long[]in=new long[n];for(int i=0;i<n;i++)in[i]=nextLong();
            shuffle(in);
            Arrays.sort(in);
            return in;
        }
        public Integer[] IntegerArr(int n) throws IOException {
            Integer[]in=new Integer[n];for(int i=0;i<n;i++)in[i]=nextInt();
            return in;
        }
        public Long[] LongArr(int n) throws IOException {
            Long[]in=new Long[n];for(int i=0;i<n;i++)in[i]=nextLong();
            return in;
        }
        public String nextLine() throws IOException {
            return br.readLine();
        }
     
        public int nextInt() throws IOException {
            return Integer.parseInt(next());
        }
     
        public double nextDouble() throws IOException {
            return Double.parseDouble(next());
        }
     
        public char nextChar() throws IOException {
            return next().charAt(0);
        }
     
        public long nextLong() throws IOException {
            return Long.parseLong(next());
        }
     
        public boolean ready() throws IOException {
            return br.ready();
        }
     
        public void waitForInput() throws InterruptedException {
            Thread.sleep(3000);
        }
        
    }
    static void sort(int[]in) {
    	shuffle(in);
        Arrays.sort(in);
    }
    static void sort(long[]in) {
    	shuffle(in);
        Arrays.sort(in);
    }
    static void shuffle(int[]in) {
        for(int i=0;i<in.length;i++) {
            int idx=(int)(Math.random()*in.length);
            int tmp=in[i];
            in[i]=in[idx];
            in[idx]=tmp;
        }
    }
    static void shuffle(long[]in) {
        for(int i=0;i<in.length;i++) {
            int idx=(int)(Math.random()*in.length);
            long tmp=in[i];
            in[i]=in[idx];
            in[idx]=tmp;
        }
    }
}