Piggy (who, in his spare time, manages the Interstellar Connectivity Protocol Commission) is facing a delicate hardware conundrum. The latest communication grid, consisting of $n$ relay stations connected by $n-1$ fiber-optic links to form a tree structure, is finally ready for deployment. However, the system must be powered on with extreme caution.

The activation process involves firing laser pulses along specific paths. A path is defined as the unique simple route between two stations. Due to the catastrophic risk of “Quantum Backflow Interference” — a phenomenon that keeps the commission’s lawyers awake at night — the following protocol must be strictly observed:

• Transmission paths must be established one by one.
• To prevent power surges, each newly established path may share at most one station with the set of stations already activated by any previous path.

Formally, let $S$ be the set of currently activated stations. For any new path $P$ consisting of a set of stations $V(P)$, the condition $|V(P) \cap S| \le 1$ must hold. Once a path is successfully fired, all stations along that path are considered part of the activated set $S$.

Your mission, should you choose to accept it, is to determine the minimum number of laser pulses required to activate every station in the entire network and provide one such sequence of paths to satisfy the legal department.

The illustration of the first two sample test cases. Note that in Case 2, the second pulse shares only station 2 with the first, satisfying the non-interference rule.

Input

There are multiple test cases. The first line of the input contains an integer $T$ ($1 \le T \le 10^4$) indicating the number of test cases. For each test case:

The first line contains an integer $n$ ($2 \le n \le 3 \times 10^5$), the number of stations in the grid.

For the following $n-1$ lines, the $i$-th line contains two integers $u_i$ and $v_i$ ($1 \le u_i, v_i \le n, u_i \neq v_i$), describing a bidirectional fiber-optic link between station $u_i$ and station $v_i$.

It is guaranteed that the links form a tree and that the sum of $n$ over all test cases does not exceed $3 \times 10^5$.

Output

For each test case, output the minimum number of paths $k$ on the first line. Following this, output $k$ lines, each containing two integers $a_i$ and $b_i$, representing the endpoints of the $i$-th path in the sequence. Note that $a_i$ may equal $b_i$ if the path consists of a single station.

If multiple optimal sequences exist, any one that strictly follows the non-interference protocol will be accepted.

Examples

Input 1

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

Output 1

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