Background

At the SCP2019 competition, a problem involving numbers on a tree ruined Xiao P's dream of getting into THU. Now, at the TP social event, Xiao P has used this same tree problem to fulfill half of that THU dream.

Description

Simplified problem statement:

Given a tree with $n$ nodes labeled $1 \sim n$, each edge initially has a number $0$. You can perform several operations. Each operation consists of choosing two nodes $x$ and $y$ that have never been chosen before, and incrementing the numbers on the edges along the simple path between $x$ and $y$ by one. It is easy to see that you can perform at most $\lfloor \frac{n}{2} \rfloor$ operations. You need to ensure that the maximum frequency of any number appearing on the edges is minimized. If there are multiple solutions, you may output any one of them.

Input

The input contains multiple test cases.

The first line contains an integer $T$, representing the number of test cases. The following lines contain the test cases.

For each test case:

The first line contains a positive integer $n$, representing the number of nodes in the tree.

The next $n-1$ lines each contain two positive integers $u, v$, describing an edge in the tree. It is guaranteed that the input forms a tree.

Output

For each test case:

The first line should contain a positive integer $k$, representing the number of operations you perform.

The next $k$ lines should each contain two positive integers $x_i, y_i$, representing one operation you choose.

You must ensure that $0 \le k \le \lfloor \frac{n}{2} \rfloor$, that $x_1, y_1, x_2, y_2, \dots, x_k, y_k$ are all distinct and are integers between $1$ and $n$, and that your operation method is optimal.

Examples

Input 1

1
6
1 2
1 3
3 4
1 5
5 6

Output 1

2
1 6
3 5

Subtasks

For all data, $1 \le T \le 4 \times 10^4$, $1 \le n \le 10^5$, $1 \le \sum n \le 5 \times 10^5$, $1 \le u, v \le n$, $u \ne v$.

Note

If you cannot realize your THU dream, you might consider its neighbor as a lower-tier alternative.