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 dbg(x...) \
	do { \
		cout << #x << " -> "; \
		err(x); \
	} while (0)

void err() {
    cout << endl;
}

template<class T, class... Ts>
void err(T arg, Ts &... args) {
    cout << arg << ' ';
    err(args...);
}

void read() {}

template <class T, class... Ts>
void read(T &arg, Ts &... args) {
    T f = 1;
    char ch;
    arg = 0;
    for (ch = getchar(); ch < '0' || ch > '9'; ch = getchar()) {
        if (ch == '-') f = -1;
    }
    for (; ch >= '0' && ch <= '9'; ch = getchar()) arg = arg * 10 + ch - '0';
    arg *= f;
    read(args...);
}

template <class T>
void myHash(T a[], int n, T w[] = nullptr) {
    set<T> st;
    for (int i = 0; i < n; i++) {
        st.insert(a[i]);
    }
    int tot = 0;
    map<T, int> mp;
    for (T x : st) {
        mp[x] = ++tot;
    }
    for (int i = 0; i < n; i++) {
        a[i] = mp[a[i]];
    }
    if (w != nullptr) {
        for (pair<T, int> p : mp) {
            w[p.second] = p.first;
        }
    }
}

typedef long long ll;
typedef pair<int, int> pii;

const int maxn = 1e5 + 7;
const int inf = 0x3f3f3f3f;
const int mod = 998244353;

set<int> G[maxn];
int f[maxn];

vector<pii> edge;

void del(int u, int v) {
    G[u].erase(v);
    G[v].erase(u);
    edge.emplace_back(u, v);
}

void dfs(int u, int fa) {
    f[u] = 0;
    vector<int> vec;
    vector<int> tmp;
    for (int v : G[u]) {
        if (v == fa) continue;
        dfs(v, u);
        if (f[v] == 1) {
            tmp.push_back(v);
        } else {
            if (vec.size() == 2) {
                tmp.push_back(v);
            } else {
                vec.push_back(v);
            }
        }
    }
    for (int v : tmp) {
        del(u, v);
    }
    if (vec.size() < 2) {
        f[u] = 0;
    } else {
        f[u] = 1;
    }
}

bool vis[maxn];

int dfs2(int u, int fa) {
    vis[u] = true;
    for (int v : G[u]) {
        if (v == fa) continue;
        return dfs2(v, u);
    }
    return u;
}

void run() {
    int n;
    read(n);
    for (int i = 1; i <= n; i++) {
        G[i].clear();
        f[i] = 0;
        vis[i] = false;
    }
    edge.clear();
    for (int i = 1; i < n; i++) {
        int u, v;
        read(u, v);
        G[u].insert(v);
        G[v].insert(u);
    }
    dfs(1, 0);

    vector<pii> add;
    for (int i = 1; i <= n; i++) {
        if (vis[i] || G[i].size() == 2) continue;
        add.emplace_back(i, dfs2(i, 0));
    }
    printf("%d\n", (int) edge.size());
    for (int i = 0; i < edge.size(); i++) {
        printf("%d %d %d %d\n", edge[i].first, edge[i].second, add[i].second, add[i + 1].first);
    }
}

/*

*/

int main() {

    int T = 1;
    read(T);
    while (T--) {
        run();
    }

    return 0;
}