As a child, Steve yearned for the mines! His mine can be represented as a tree$^{\text{∗}}$ of $n$ nodes.

Unfortunately, Steve's mine has been infiltrated by his greatest nemesis, Herobrine! At any time, Herobrine is hiding in exactly one node; initially, he may be in any of them. Steve can perform the following operations:

• $1\,\,x$ — Check if Herobrine is currently in node $x$. If he is, Steve catches him. Otherwise, Herobrine may or may not move to any adjacent node (except the one you just checked).
• $2\,\,x$ — Destroy all edges connected to node $x$; Herobrine will no longer be able to use them. Afterwards, Herobrine may or may not move to any adjacent node.

Find a sequence of at most $\left\lfloor \frac{5}{4} \cdot n \right\rfloor$ operations that will guarantee Steve catches Herobrine, regardless of Herobrine's initial location and moves. We have a proof that, under the given constraints, this is always possible.

$^{\text{∗}}$A tree is a connected graph without cycles.

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($2 \le n \le 2 \cdot 10^5$) — the number of nodes.

Each of the next $n − 1$ lines contains two integers $u$ and $v$ ($1 \le u, v \le n$), describing an edge between nodes $u$ and $v$.

It is guaranteed that the given edges form a tree.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.

Output

For each test case, first output a single integer $k$ ($1 \le k \le \left\lfloor \frac{5}{4} \cdot n \right\rfloor$) — the number of operations you wish to perform.

Then output $k$ lines. Line $i$ ($1 \le i \le k$) should contain two integers $t_i$ and $x_i$ ($1 \le t_i \le 2$, $1 \le x_i \le n$), indicating that the $i$-th operation you wish to perform is operation $t_i$ on node $x_i$.

Note

In the first test case, the tree is as follows:

Initially, Herobrine may be in either of the nodes. After the first operation, which checks node $1$, if Herobrine was in node $1$, he would be caught, so the only possible node he could be in after the operation is node $2$ (he cannot move to node $1$ since it was just checked). Therefore, after the second operation, which checks node $2$, he must have been caught.

In the second test case, the tree is as follows:

Initially, Herobrine may be in any of the nodes $[1, 2, 3, 4]$. After the first operation, Herobrine can only be in nodes $[1, 3, 4]$. The second operation destroys all edges adjacent to node $2$. Since all the edges connected to nodes $1$, $3$, and $4$ are now destroyed, Herobrine is unable to move any more no matter where he is located. So after checking those three nodes in operations $3$, $4$, and $5$, he is guaranteed to have been caught.