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;
#define int long long
vector<pair<int, int>> ans, a;
vector<bool> us;
vector<vector<int>> g;
int c = 0;


void dfs(int v, int p) {
    int cnt = 0;
    for (auto u:g[v]) {
        if (u == p) continue;
        dfs(u, v);
        if (!us[u]) cnt++;
    }
    if (cnt > 1) {
        if (p != -1) {
            us[v] = true;
            ans.push_back({v, p});
        }
        for (auto u:g[v]) {
            if (cnt == 2) break;
            if (u == p) continue;
            if (!us[u]) cnt--, ans.push_back({u, v}), us[u] = true;
        }
    }
}


void dfs1(int v, int p, int col) {
    int cnt = 0;
    for (auto u:g[v]) {
        if (u == p) continue;
        if (!us[u]) {
            cnt++;
            dfs1(u, v, col);
        } else{
            dfs1(u, v, ++c);
        }
    }
    if (cnt == 0 || (cnt == 1 && us[v])) {
        if (a[col].first == -1) a[col].first = v;
        else a[col].second = v;
    }
}


signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int t;
    cin >> t;
    for (int z = 0; z < t; ++z) {
        int n;
        cin >> n;
        ans.clear(), c = 0;
        g.assign(n, {}), us.assign(n, false);
        for (int i = 0; i < n - 1; ++i) {
            int v, u;
            cin >> v >> u;
            g[v - 1].push_back(u - 1);
            g[u - 1].push_back(v - 1);
        }
        us[0] = true;
        dfs(0, -1);
        a.assign(ans.size() + 1, {-1, -1});
        dfs1(0, -1, 0);
        for (int i = 0; i <= ans.size(); ++i) {
            if (a[i].second == -1) a[i].second = a[i].first;
        }
        cout << ans.size() << endl;
        for (int i = 0; i < ans.size(); ++i) {
            cout << ans[i].first + 1 << " " << ans[i].second + 1 << " " << a[i].second + 1 << " " << a[i + 1].first + 1
                 << endl;
        }
    }
}