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;

const int N = 2.1e5;

vector<int> t[N];
vector<int> endpts[N];
int dp[N][2], verts[N][2];
int total[N], mins[N];
int which_path[N];
int npath = 0;

int smallest(int v, int par, int no) {
    int small = 1e9;
    int who = -1;
    for (int u : t[v]) {
        if (u == par) continue;
        if (dp[u][0] - mins[u] < small && u != no) {
            small = dp[u][0] - mins[u];
            who = u;
        }
    }
    return who;
}

void dfs(int v, int par = -1) {
    for (int u : t[v]) {
        if (u == par) continue;
        dfs(u, v);
        mins[u] = min(dp[u][0], dp[u][1]);
        total[v] += mins[u];
    }
    verts[v][0] = smallest(v, par, -1);
    verts[v][1] = smallest(v, par, verts[v][0]);
    if (verts[v][0] == -1) {
        dp[v][0] = 1;
        dp[v][1] = 1e9;
        return;
    }
    int cst = total[v] - mins[verts[v][0]] + dp[verts[v][0]][0];
    dp[v][0] = min(total[v] + 1, cst);
    if (verts[v][1] == -1) {
        dp[v][1] = 1e9;
    } else {
        dp[v][1] = total[v] - mins[verts[v][0]] - mins[verts[v][1]] + dp[verts[v][0]][0] + dp[verts[v][1]][0] - 1;
    }
}

void construct(int v, int mode, int path, int par = -1) {
    which_path[v] = path;
    set<int> no;
    if (mode == 1) {
        construct(verts[v][0], 0, path, v);
        construct(verts[v][1], 0, path, v);
        no = {verts[v][0], verts[v][1]};
    } else if (mode == 0 && dp[v][0] < total[v] + 1) {
        construct(verts[v][0], 0, path, v);
        no = {verts[v][0]};
    } else {
        endpts[path].push_back(v);
    }
    for (int u : t[v]) {
        if (u == par || no.count(u)) continue;
        int mode = dp[u][0] < dp[u][1] ? 0 : 1;
        if (mode == 0) endpts[npath + 1].push_back(u);
        construct(u, mode, ++npath, v);
    }
}
void solve() {
    int n;
    cin >> n;
    for (int i = 0; i + 1 < n; ++i) {
        int u, v;
        cin >> u >> v;
        --u, --v;
        t[u].push_back(v);
        t[v].push_back(u);
    }
    dfs(0);
    vector<int> dsu(n);
    iota(dsu.begin(), dsu.end(), 0);
    function<int(int)> Find = [&](int k) -> int { if (dsu[k] == k) return k; else return dsu[k] = Find(dsu[k]); };
    vector<tuple<int, int, int, int>> ans;
    if (dp[0][0] < dp[0][1]) endpts[0].push_back(0);
    construct(0, dp[0][0] < dp[0][1] ? 0 : 1, 0);
    for (int i = 0; i < n; ++i) {
        for (int v : t[i]) {
            int wi = Find(which_path[i]), wv = Find(which_path[v]);
            if (wi != wv) {
                ans.emplace_back(i + 1, v + 1, endpts[wi][0] + 1, endpts[wv][0] + 1);
                endpts[wi][0] = endpts[wv][0] = endpts[wi][1];
                endpts[wi][1] = endpts[wv][1] = endpts[wv][1];
                dsu[wi] = wv;
            }
        }
    }
    assert(ans.size() == min(dp[0][0], dp[0][1]) - 1);
    cout << min(dp[0][0], dp[0][1]) - 1 << "\n";
    for (auto [a, b, c, d] : ans) {
        cout << a << " " << b << " " << c << " " << d << "\n";
    }
    npath = 0;
    for (int i = 0; i < n; ++i) {
        t[i].clear(), endpts[i].clear();
        which_path[i] = 0;
        dp[i][0] = dp[i][1] = verts[i][0] = verts[i][1] = mins[i] = total[i] = 0;
    }
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  int t;
  cin >> t;
  while (t--) solve();
  return 0;
}