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:
// coached by rainboy
import java.io.*;
import java.util.*;

public class CF1521D extends PrintWriter {
	CF1521D() { super(System.out); }
	Scanner sc = new Scanner(System.in);
	public static void main(String[] $) {
		CF1521D o = new CF1521D(); o.main(); o.flush();
	}

	int[] eo; int[][] ej;
	void append(int i, int j) {
		int o = eo[i]++;
		if (o >= 2 && (o & o - 1) == 0)
			ej[i] = Arrays.copyOf(ej[i], o << 1);
		ej[i][o] = j;
	}
	int[] x1, y1, x2, y2; int cnt;
	int x;
	int dfs(int p, int i) {
		int j1 = -1, z1 = -1, j2 = -1, z2 = -1;
		for (int o = eo[i]; o-- > 0; ) {
			int j = ej[i][o];
			if (j != p) {
				int z = dfs(i, j);
				if (z == -1)
					continue;
				if (j1 == -1) {
					j1 = j;
					z1 = z;
				} else if (j2 == -1) {
					j2 = j;
					z2 = z;
				} else {
					x1[cnt] = i; y1[cnt] = j;
					x2[cnt] = x; y2[cnt] = j; x = z;
					cnt++;
				}
			}
		}
		if (j2 != -1) {
			x1[cnt] = p; y1[cnt] = i;
			x2[cnt] = x; y2[cnt] = z1; x = z2;
			cnt++;
			return -1;
		}
		if (j1 != -1)
			return z1;
		return i;
	}
	void main() {
		int t = sc.nextInt();
		while (t-- > 0) {
			int n = sc.nextInt();
			eo = new int[n]; ej = new int[n][2];
			x1 = new int[n]; y1 = new int[n]; x2 = new int[n]; y2 = new int[n]; cnt = 0;
			for (int h = 0; h < n - 1; h++) {
				int i = sc.nextInt() - 1;
				int j = sc.nextInt() - 1;
				append(i, j);
				append(j, i);
			}
			x = 0;
			while (eo[x] != 1)
				x++;
			dfs(x, ej[x][0]);
			println(cnt);
			for (int h = 0; h < cnt; h++)
				println((x1[h] + 1) + " " + (y1[h] + 1) + " " + (x2[h] + 1) + " " + (y2[h] + 1));
		}
	}
}