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 CPP):

Solution:
#include <algorithm>
#include <cstdio>
#include <map>
#include <queue>
const int N = 1e5 + 7;
using namespace std;
struct edge
{
    int next, v;
    edge() {}
    edge(int v, int next) : v(v), next(next) {}
} e[N << 1], ed[N << 1];
int head[N], hd[N], tot, ctot, vis[N], vis2[N], node[N], T, u[N], v[N];
int sum, n;
map<pair<int, int>, int> ansd;
queue<int> r;
void addedge(int u, int v)
{
    e[tot] = edge(v, head[u]);
    head[u] = tot++;
}
void adde(int u, int v)
{
    ed[ctot] = edge(v, hd[u]);
    hd[u] = ctot++;
}
int dfs(int u, int fa)
{
    int tmp = 0;
    for (int i = head[u]; ~i; i = e[i].next)
    {
        int v = e[i].v;
        if (v == fa) continue;
        if (dfs(v, u))
        {
            ++tmp;
            if (vis[u] < 2)
                ++vis[u];
            else
                ansd[{u, v}] = 1;
        }
        else
            ansd[{u, v}] = 1;
    }
    if (tmp >= 2)
    {
        sum += tmp - 2;
        if (u != 1) ++sum;
        return 0;
    }
    return 1;
}
void dfs2(int u, int fa)
{
    int son = 0;
    vis2[u] = 1;
    for (int i = hd[u]; ~i; i = ed[i].next)
    {
        int v = ed[i].v;
        if (v == fa) continue;
        dfs2(v, u);
        ++son;
    }
    if (son == 0) r.push(u);
    if (son == 1 && fa == -1) r.push(u);
}
int main()
{
    scanf("%d", &T);
    while (T--)
    {
        ansd.clear();
        scanf("%d", &n);
        for (int i = 1; i <= n; ++i) hd[i] = head[i] = -1, vis[i] = vis2[i] = node[i] = 0;
        tot = ctot = 0;
        sum = 0;
        for (int i = 1; i < n; i++)
        {
            scanf("%d%d", &u[i], &v[i]);
            addedge(u[i], v[i]);
            addedge(v[i], u[i]);
        }
        dfs(1, -1);
        for (int i = 1; i < n; ++i)
            if (0 == ansd.count({u[i], v[i]}) + ansd.count({v[i], u[i]})) adde(u[i], v[i]), adde(v[i], u[i]);
        for (int i = 1; i <= n; ++i)
        {
            if (vis2[i]) continue;
            if (0 == ~hd[i]) r.push(i);
            dfs2(i, -1);
        }
        r.pop();
        printf("%d\n", sum);
        for (auto i : ansd)
        {
            printf("%d %d %d", i.first.first, i.first.second, r.front());
            r.pop();
            printf(" %d\n", r.front());
            r.pop();
        }
        r.pop();
    }
    return 0;
}