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 <bits/stdc++.h>
using namespace std;

vector<bool> removed, visited;
vector<array<int, 2>> edges, end_points;
vector<vector<int>> adj;

int dfs_cut(int u, int e) {
    int cnt = 0;
    for (int i : adj[u]) {
        if (i != e) {
            int v = u ^ edges[i][0] ^ edges[i][1];
            cnt += dfs_cut(v, i);
        }
    }

    if (cnt <= 1) {
        return 1;
    } else {
        if (e >= 0) {
            removed[e] = true;
        }
        for (int i : adj[u]) {
            if (i == e || removed[i])
                continue;
            if (cnt == 2)
                break;
            removed[i] = true;
            cnt--;
        }
        return 0;
    }
}

int dfs_connect(int u, int e) {
    visited[u] = true;
    vector<int> rets;
    for (int i : adj[u]) {
        if (i != e && !removed[i]) {
            int v = u ^ edges[i][0] ^ edges[i][1];
            rets.push_back(dfs_connect(v, i));
        }
    }

    if (int(rets.size()) == 1) {
        if (e == -1) {
            end_points.push_back({u, rets[0]});
            return -1;
        } else {
            return rets[0];
        }
    } else {
        if (rets.empty()) {
            if (e == -1) {
                end_points.push_back({u, u});
                return -1;
            } else {
                return u;
            }
        } else {
            end_points.push_back({rets[0], rets[1]});
        }
        return -1;
    }
}

void solve() {
    int n;
    cin >> n;

    removed.assign(n - 1, false);
    edges.assign(n - 1, {-1, -1});
    adj.assign(n, {});

    int idx = 0;
    for (auto& e : edges) {
        cin >> e[0] >> e[1];
        adj[--e[0]].push_back(idx);
        adj[--e[1]].push_back(idx);
        idx++;
    }

    dfs_cut(0, -1);

    visited.assign(n, false);
    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            dfs_connect(i, -1);
        }
    }

    cout << int(end_points.size()) - 1 << '\n';
    for (int i = 0, j = 0; i < n - 1; i++) {
        if (removed[i]) {
            cout << edges[i][0] + 1 << ' ' << edges[i][1] + 1 << ' ';
            cout << end_points[j][1] + 1 << ' ' << end_points[j + 1][0] + 1 << '\n';
            j++;
        }
    }

    edges.clear();
    end_points.clear();
    adj.clear();
}

int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int tt;
    cin >> tt;
    while (tt--) {
        solve();
    }
    return 0;
}