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 MAXN = 1e5, INF = 2e8;
int N, P[MAXN], D[MAXN], DP[5][MAXN];
vector<int> G[MAXN];

void buildParents() {

  queue<int> Q;
  Q.push(0);
  P[0] = 0;

  while(!Q.empty()) {
    int u = Q.front(); Q.pop();

    for(int v : G[u]) if(P[v] == -1) {
      P[v] = u;
      Q.push(v);
    }
  }
}

void fillDP() {

  typedef pair<int, bool> state;

  stack<state> S;
  S.emplace(0, false);

  while(!S.empty()) {
    state s = S.top(); S.pop();

    int u = s.first;
    bool ready = s.second;

    if(ready) {
      int sum = 0, deg = D[u] - (u != 0);
      for(int v : G[u]) if(v != P[u]) sum += DP[4][v];

      DP[0][u] = sum + deg;

      sort(G[u].begin(), G[u].end(), [&](int x, int y) {
        int delta_x = (x != P[u] ? DP[3][x] - DP[4][x] : INF), delta_y = (y != P[u] ? DP[3][y] - DP[4][y] : INF);
        return delta_x != delta_y ? delta_x < delta_y : x < y;
      });

      if(deg >= 1) {
        DP[1][u] = sum + (deg - 1) + (DP[3][G[u][0]] - DP[4][G[u][0]]);
      }
      else {
        DP[1][u] = INF;
      }

      if(deg >= 2) {
        DP[2][u] = sum + (deg - 2) + (DP[3][G[u][0]] - DP[4][G[u][0]]) + (DP[3][G[u][1]] - DP[4][G[u][1]]);
      }
      else {
        DP[2][u] = INF;
      }

      DP[3][u] = min({DP[0][u], DP[1][u]});
      DP[4][u] = min({DP[0][u], DP[1][u], DP[2][u]});
    }

    else {
      S.emplace(u, true);

      for(int v : G[u]) if(v != P[u]) S.emplace(v, false);
    }
  }
}

typedef pair<int, int> pii;

int main() {
  ios::sync_with_stdio(0); cin.tie(0);
  cout << boolalpha;

  int T; cin >> T;
  while(T--) {
    cin >> N;
    for(int i = 0; i < N; ++i) {
      G[i].clear();

      for(int k = 0; k < 5; ++k) {
        DP[k][i] = -1;
      }
      
      P[i] = -1;
      D[i] = 0;
    }

    for(int _ = 0; _ < N-1; ++_) {
      int a, b; cin >> a >> b;
      --a;
      --b;

      G[a].push_back(b);
      G[b].push_back(a);

      ++D[a];
      ++D[b];
    }

    buildParents();
    fillDP();

    int ans = DP[4][0];
    
    vector<pii> ADD, REMOVE;

    vector<bool> V(N, false);

    vector<int> A, B;

    queue<int> R; R.push(0);

    while(!R.empty()) {
      int r = R.front(); R.pop();

      int b = 0; 
      for(int k = 0; k < 3; ++k) if(DP[k][r] == DP[4][r]) {
        b = k;
        break;
      }

      for(int k = b; k < G[r].size(); ++k) if(P[r] != G[r][k]) {
        R.push(G[r][k]);

        REMOVE.emplace_back(r, G[r][k]);
      }

      if(b == 0) {
        A.push_back(r);
        B.push_back(r);
      } 

      if(b == 1) {
        A.push_back(r);
      }

      if(b > 0) {
        queue<int> Q;
        for(int k = 0; k < b; ++k) Q.push(G[r][k]);

        while(!Q.empty()) {
          int q = Q.front(); Q.pop();
          int b = 0;

          for(int k = 0; k < 2; ++k) if(DP[k][q] == DP[3][q]) {
            b = k;
            break;
          }

          if(b == 0) {
            if(A.size() == B.size()) A.push_back(q);
            else B.push_back(q);
          }

          for(int k = 0; k < b; ++k) Q.push(G[q][k]);

          for(int k = b; k < G[q].size(); ++k) if(P[q] != G[q][k]) {
            R.push(G[q][k]);

            REMOVE.emplace_back(q, G[q][k]);
          }
        }
      }
    }

    for(int i = 1; i < A.size(); ++i) ADD.emplace_back(A[i], B[i-1]);

    cout << ans << '\n';
    for(int i = 0; i < REMOVE.size(); ++i) 
      cout << REMOVE.at(i).first+1 << ' ' << REMOVE.at(i).second+1 << ' '
          << ADD.at(i).first+1 << ' ' << ADD.at(i).second+1 << '\n';
  }

  return 0;
}