#include <bits/stdc++.h>
#pragma GCC target("avx2")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
using namespace std;
template <class T, class U>
ostream &operator<<(ostream &os, const pair<T, U> &p) {
  os << '(' << p.first << ',' << p.second << ')';
  return os;
}
template <class T>
ostream &operator<<(ostream &os, const vector<T> &v) {
  os << '{';
  for (int i = 0; i < (int)v.size(); i++) {
    if (i) {
      os << ',';
    }
    os << v[i];
  }
  os << '}';
  return os;
}
ostream &operator<<(ostream &os, const set<int> &se) {
  os << '{';
  int now = 0;
  for (auto x : se) {
    if (now) {
      os << ',';
    }
    os << x;
    now++;
  }
  os << '}';
  return os;
}
void debugg() { cerr << endl; }
template <class T, class... Args>
void debugg(const T &x, const Args &...args) {
  cerr << " " << x;
  debugg(args...);
}
using namespace std;
const int inf = (1 << 30) - 1;
const long long linf = 1LL << 61;
const int MAX = 510000;
int dy[8] = {0, 1, 0, -1, 1, -1, -1, 1};
int dx[8] = {-1, 0, 1, 0, 1, -1, 1, -1};
const double pi = acos(-1);
const double eps = 1e-8;
template <typename T1, typename T2>
inline bool chmin(T1 &a, T2 b) {
  if (a > b) {
    a = b;
    return true;
  } else
    return false;
}
template <typename T1, typename T2>
inline bool chmax(T1 &a, T2 b) {
  if (a < b) {
    a = b;
    return true;
  } else
    return false;
}
template <typename T>
inline void print(T &a) {
  int sz = a.size();
  for (auto itr = a.begin(); itr != a.end(); itr++) {
    cout << *itr;
    sz--;
    if (sz) cout << " ";
  }
  cout << "\n";
}
template <typename T1, typename T2>
inline void print2(T1 a, T2 b) {
  cout << a << " " << b << "\n";
}
template <typename T1, typename T2, typename T3>
inline void print3(T1 a, T2 b, T3 c) {
  cout << a << " " << b << " " << c << "\n";
}
void mark() {
  cout << "#"
       << "\n";
}
long long pcount(long long x) { return __builtin_popcountll(x); }
const int mod = 998244353;
void solve() {
  int n;
  cin >> n;
  vector<long long> a(n), b(n), m(n);
  map<long long, vector<vector<long long> > > mp;
  for (int i = 0; i < (n); i++) {
    cin >> a[i] >> b[i] >> m[i];
    mp[a[i] + b[i] - m[i]].push_back(vector<long long>{
        a[i] + min(0LL, b[i] - m[i]), max(0LL, a[i] - m[i]), i});
  }
  int ans = 0;
  vector<long long> A(n), B(n);
  for (auto v : mp) {
    sort((v.second).begin(), (v.second).end());
    vector<long long> r;
    for (auto x : v.second) {
      if (r.empty() || x[1] > r.back()) {
        ans++;
        r.push_back(x[0]);
      }
      A[x[2]] = a[x[2]] - r.back();
      B[x[2]] = m[x[2]] - A[x[2]];
    }
  }
  cout << ans << "\n";
  for (int i = 0; i < (n); i++) cout << A[i] << " " << B[i] << "\n";
}
int main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  int t = 1;
  cin >> t;
  while (t--) {
    solve();
  }
}

### Prompt

Construct a CPP code solution to the problem outlined:

The chef has cooked n dishes yet again: the i-th dish consists of a_i grams of fish and b_i grams of meat. 

Banquet organizers consider two dishes i and j equal if a_i=a_j and b_i=b_j at the same time.

The banquet organizers estimate the variety of n dishes as follows. The variety of a set of dishes is equal to the number of different dishes in it. The less variety is, the better.

In order to reduce the variety, a taster was invited. He will eat exactly m_i grams of food from each dish. For each dish, the taster determines separately how much fish and how much meat he will eat. The only condition is that he will eat exactly m_i grams of the i-th dish in total.

Determine how much of what type of food the taster should eat from each dish so that the value of variety is the minimum possible. If there are several correct answers, you may output any of them.

Input

The first line of input data contains an integer t (1 ≤ t ≤ 10^4) — the number of test cases.

Each test case's description is preceded by a blank line. Next comes a line that contains an integer n (1 ≤ n ≤ 2 ⋅ 10^5) — the number of dishes. Then follows n lines, i-th of which contains three integers a_i, b_i and m_i (0 ≤ a_i, b_i ≤ 10^6; 0 ≤ m_i ≤ a_i+b_i) — the mass of fish in i-th dish, the mass of meat in i-th dish and how many grams in total the taster should eat in i-th dish.

The sum of all n values for all input data sets in the test does not exceed 2 ⋅ 10^5.

Output

For each test case, print on the first line the minimum value of variety that can be achieved by eating exactly m_i grams of food (for all i from 1 to n) from a dish i.

Then print n lines that describe a way to do this: the i-th line should contain two integers x_i and y_i (0 ≤ x_i ≤ a_i; 0 ≤ y_i ≤ b_i; x_i+y_i=m_i), where x_i is how many grams of fish the taster should eat from i-th dish, and y_i is how many grams of meat.

If there are several ways to achieve a minimum balance, print any of them.

Example

Input


5

3
10 10 2
9 9 0
10 9 1

2
3 4 1
5 1 2

3
7 2 5
6 5 4
5 5 6

1
13 42 50

5
5 7 12
3 1 4
7 3 7
0 0 0
4 1 5


Output


1
1 1
0 0
1 0
2
0 1
1 1
2
3 2
0 4
1 5
1
8 42
2
5 7
3 1
4 3
0 0
4 1

### Response

```cpp
#include <bits/stdc++.h>
#pragma GCC target("avx2")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
using namespace std;
template <class T, class U>
ostream &operator<<(ostream &os, const pair<T, U> &p) {
  os << '(' << p.first << ',' << p.second << ')';
  return os;
}
template <class T>
ostream &operator<<(ostream &os, const vector<T> &v) {
  os << '{';
  for (int i = 0; i < (int)v.size(); i++) {
    if (i) {
      os << ',';
    }
    os << v[i];
  }
  os << '}';
  return os;
}
ostream &operator<<(ostream &os, const set<int> &se) {
  os << '{';
  int now = 0;
  for (auto x : se) {
    if (now) {
      os << ',';
    }
    os << x;
    now++;
  }
  os << '}';
  return os;
}
void debugg() { cerr << endl; }
template <class T, class... Args>
void debugg(const T &x, const Args &...args) {
  cerr << " " << x;
  debugg(args...);
}
using namespace std;
const int inf = (1 << 30) - 1;
const long long linf = 1LL << 61;
const int MAX = 510000;
int dy[8] = {0, 1, 0, -1, 1, -1, -1, 1};
int dx[8] = {-1, 0, 1, 0, 1, -1, 1, -1};
const double pi = acos(-1);
const double eps = 1e-8;
template <typename T1, typename T2>
inline bool chmin(T1 &a, T2 b) {
  if (a > b) {
    a = b;
    return true;
  } else
    return false;
}
template <typename T1, typename T2>
inline bool chmax(T1 &a, T2 b) {
  if (a < b) {
    a = b;
    return true;
  } else
    return false;
}
template <typename T>
inline void print(T &a) {
  int sz = a.size();
  for (auto itr = a.begin(); itr != a.end(); itr++) {
    cout << *itr;
    sz--;
    if (sz) cout << " ";
  }
  cout << "\n";
}
template <typename T1, typename T2>
inline void print2(T1 a, T2 b) {
  cout << a << " " << b << "\n";
}
template <typename T1, typename T2, typename T3>
inline void print3(T1 a, T2 b, T3 c) {
  cout << a << " " << b << " " << c << "\n";
}
void mark() {
  cout << "#"
       << "\n";
}
long long pcount(long long x) { return __builtin_popcountll(x); }
const int mod = 998244353;
void solve() {
  int n;
  cin >> n;
  vector<long long> a(n), b(n), m(n);
  map<long long, vector<vector<long long> > > mp;
  for (int i = 0; i < (n); i++) {
    cin >> a[i] >> b[i] >> m[i];
    mp[a[i] + b[i] - m[i]].push_back(vector<long long>{
        a[i] + min(0LL, b[i] - m[i]), max(0LL, a[i] - m[i]), i});
  }
  int ans = 0;
  vector<long long> A(n), B(n);
  for (auto v : mp) {
    sort((v.second).begin(), (v.second).end());
    vector<long long> r;
    for (auto x : v.second) {
      if (r.empty() || x[1] > r.back()) {
        ans++;
        r.push_back(x[0]);
      }
      A[x[2]] = a[x[2]] - r.back();
      B[x[2]] = m[x[2]] - A[x[2]];
    }
  }
  cout << ans << "\n";
  for (int i = 0; i < (n); i++) cout << A[i] << " " << B[i] << "\n";
}
int main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  int t = 1;
  cin >> t;
  while (t--) {
    solve();
  }
}

```