#include <bits/stdc++.h>
using namespace std;
long long powmod(long long base, long long exponent, long long mod) {
  long long result = 1;
  while (exponent > 0) {
    if (exponent % 2 == 0) {
      exponent /= 2;
      base = (base * base) % mod;
    } else {
      result = (result * base) % mod;
      exponent /= 2;
      base = (base * base) % mod;
    }
  }
  return result;
}
bool decresing(long long x, long long y) { return x > y; }
long long trin(long long start, long long stop) {
  return (stop - start + 1) * (stop + start) / 2;
}
bool sortvectorf(pair<long long, long long> a, pair<long long, long long> b) {
  return ((a.first > b.first) || (a.first == b.first && a.second > b.second));
}
bool sortvectordiv(pair<long long, long long> a, pair<long long, long long> b) {
  return a.first * b.second > b.first * a.second;
}
bool sortvectorfv(pair<long long, long long> a, pair<long long, long long> b) {
  return ((a.first > b.first) || (a.first == b.first && a.second < b.second));
}
bool sortvectors(pair<long long, long long> a, pair<long long, long long> b) {
  return ((a.second > b.second) || (a.second == b.second && a.first > b.first));
}
bool negasortvectorf(pair<long long, long long> a,
                     pair<long long, long long> b) {
  return ((a.first < b.first) || (a.first == b.first && a.second < b.second));
}
bool negasortvectors(pair<long long, long long> a,
                     pair<long long, long long> b) {
  return ((a.second < b.second) || (a.second == b.second && a.first < b.first));
}
vector<vector<long long>> findPermutationsI(vector<long long>& a) {
  sort(a.begin(), a.end());
  vector<vector<long long>> sol;
  do {
    sol.push_back(a);
  } while (next_permutation(a.begin(), a.end()));
  return sol;
}
vector<vector<string>> findPermutationsS(vector<string>& a) {
  sort(a.begin(), a.end());
  vector<vector<string>> sol;
  do {
    sol.push_back(a);
  } while (next_permutation(a.begin(), a.end()));
  return sol;
}
long long gcd(long long a, long long b) {
  if (a == 0) {
    return b;
  }
  if (b == 0) {
    return a;
  }
  return gcd(b % a, a);
}
bool isprime(long long n) {
  for (long long i = 2; i < n; i += 1) {
    if (i * i > n) {
      break;
    }
    if ((n / i) * i == n) {
      return false;
    }
  }
  return true;
}
long long fdivisor(long long n, long long fro) {
  for (long long i = 1; i < n + 1; i += 1) {
    if ((n / i) * i == n && i >= fro) {
      return i;
    }
  }
  return -1;
}
vector<long long> divlist(long long n) {
  vector<long long> curr;
  for (long long i = 2; i < n; i += 1) {
    if ((long long)i * i > n) {
      break;
    }
    if ((n / i) * i == n) {
      curr.push_back(i);
      curr.push_back(n / i);
    }
    if ((long long)i * i == n) {
      curr.pop_back();
    }
  }
  sort(curr.begin(), curr.end());
  return curr;
}
long long countdivisors(long long n, long long divd, long long rem) {
  vector<long long> divs = divlist(n);
  long long tot = 0;
  for (long long i = 0; i < divs.size(); i += 1) {
    if (divs[i] % divd == rem) {
      tot++;
    }
  }
  if (n % divd == rem) {
    tot++;
  }
  return tot;
}
long long digsum(long long num) {
  long long cr = 0;
  while (num > 0) {
    cr += num % 10;
    num /= 10;
  }
  return cr;
}
long long modInverse(long long a, long long b) {
  long long m = b;
  long long y = 0, x = 1;
  while (a > 1) {
    long long q = a / m;
    long long t = m;
    m = a % m, a = t;
    t = y;
    y = x - q * y;
    x = t;
  }
  if (x < 0) {
    x += b;
  }
  return x;
}
long long azeret(long long num, long long mod) {
  long long sil = 1;
  while (num > 1) {
    sil *= num;
    sil %= mod;
    num--;
  }
  return sil;
}
long long moddiv(long long to, long long by, long long mod) {
  to %= mod;
  while (to % by != 0) {
    to += mod;
    if (to > (by + 1) * mod) {
      return -1;
    }
  }
  return (to / by) % mod;
}
class node {
 public:
  int data1;
  int data2;
  node* nxt;
  node* bef;
  node(int dat1, int dat2, node* bif) {
    this->nxt = NULL;
    this->bef = bif;
    this->bef->nxt = this;
    this->data1 = dat1;
    this->data2 = dat2;
  }
  node(int dat1, int dat2) {
    this->nxt = NULL;
    this->bef = NULL;
    this->data1 = dat1;
    this->data2 = dat2;
  }
  node() {
    this->nxt = NULL;
    this->bef = NULL;
    this->data1 = 0;
    this->data2 = 0;
  }
  void remove() {
    this->bef->nxt = this->nxt;
    if (this->nxt != NULL) {
      this->nxt->bef = this->bef;
    }
  }
  void push(int dat1, int dat2) {
    node* next = this->nxt;
    node* curr = new node(dat1, dat2, this);
    curr->nxt = next;
    next->bef = curr;
  }
};
vector<int> subsum(vector<int> items, int limit) {
  vector<vector<short>> table(items.size() + 1, vector<short>(limit + 1));
  for (long long j = 1; j < items.size() + 1; j += 1) {
    short wt = items[j - 1];
    short val = wt;
    for (int w = 1; w < limit + 1; w++) {
      if (wt > w) {
        table[j][w] = table[j - 1][w];
      } else {
        table[j][w] = max(table[j - 1][w], (short)(table[j - 1][w - wt] + val));
      }
    }
  }
  vector<int> result;
  int w = limit;
  for (int j = items.size(); j > 0; j--) {
    bool was_added = table[j][w] != table[j - 1][w];
    if (was_added) {
      int wt = items[j - 1];
      int val = wt;
      result.push_back(j - 1);
      w -= wt;
    }
  }
  sort(result.begin(), result.end());
  return result;
}
void flush() { cout.flush(); }
bool by_first(pair<pair<long long, long long>, pair<long long, long long>> a,
              pair<pair<long long, long long>, pair<long long, long long>> b) {
  return a.first.first < b.first.first;
}
bool ff_fs(pair<pair<long long, bool>, long long> a,
           pair<pair<long long, bool>, long long> b) {
  return a.first.first < b.first.first ||
         (a.first.first == b.first.first && a.first.second && !b.first.second);
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  long long t;
  cin >> t;
  for (long long j = 0; j < t; j += 1) {
    long long n;
    cin >> n;
    vector<pair<pair<long long, bool>, long long>> crocs(2 * n);
    for (long long i = 0; i < n; i += 1) {
      cin >> crocs[2 * i].first.first;
      crocs[2 * i].first.second = true;
      crocs[2 * i].second = i;
      cin >> crocs[2 * i + 1].first.first;
      crocs[2 * i + 1].first.second = false;
      crocs[2 * i + 1].second = i;
    }
    sort(crocs.begin(), crocs.end(), ff_fs);
    vector<long long> points(n);
    long long cnt = 0, segs = 0;
    set<long long> live;
    for (long long i = 0; i < 2 * n; i += 1) {
      if (crocs[i].first.second) {
        cnt++;
        live.insert(crocs[i].second);
        continue;
      }
      if (cnt == 1) {
        points[crocs[i].second]--;
        segs++;
      }
      cnt--;
      live.erase(crocs[i].second);
      if (cnt == 1) {
        points[*live.begin()]++;
      }
    }
    long long mxp = -2;
    for (long long i = 0; i < n; i += 1) {
      if (points[i] > mxp) {
        mxp = points[i];
      }
    }
    cout << segs + mxp << endl;
  }
  return 0;
}

### Prompt

Create a solution in cpp for the following problem:

There are n segments on a Ox axis [l_1, r_1], [l_2, r_2], ..., [l_n, r_n]. Segment [l, r] covers all points from l to r inclusive, so all x such that l ≤ x ≤ r.

Segments can be placed arbitrarily — be inside each other, coincide and so on. Segments can degenerate into points, that is l_i=r_i is possible.

Union of the set of segments is such a set of segments which covers exactly the same set of points as the original set. For example:

  * if n=3 and there are segments [3, 6], [100, 100], [5, 8] then their union is 2 segments: [3, 8] and [100, 100]; 
  * if n=5 and there are segments [1, 2], [2, 3], [4, 5], [4, 6], [6, 6] then their union is 2 segments: [1, 3] and [4, 6]. 



Obviously, a union is a set of pairwise non-intersecting segments.

You are asked to erase exactly one segment of the given n so that the number of segments in the union of the rest n-1 segments is maximum possible.

For example, if n=4 and there are segments [1, 4], [2, 3], [3, 6], [5, 7], then:

  * erasing the first segment will lead to [2, 3], [3, 6], [5, 7] remaining, which have 1 segment in their union; 
  * erasing the second segment will lead to [1, 4], [3, 6], [5, 7] remaining, which have 1 segment in their union; 
  * erasing the third segment will lead to [1, 4], [2, 3], [5, 7] remaining, which have 2 segments in their union; 
  * erasing the fourth segment will lead to [1, 4], [2, 3], [3, 6] remaining, which have 1 segment in their union. 



Thus, you are required to erase the third segment to get answer 2.

Write a program that will find the maximum number of segments in the union of n-1 segments if you erase any of the given n segments.

Note that if there are multiple equal segments in the given set, then you can erase only one of them anyway. So the set after erasing will have exactly n-1 segments.

Input

The first line contains one integer t (1 ≤ t ≤ 10^4) — the number of test cases in the test. Then the descriptions of t test cases follow.

The first of each test case contains a single integer n (2 ≤ n ≤ 2⋅10^5) — the number of segments in the given set. Then n lines follow, each contains a description of a segment — a pair of integers l_i, r_i (-10^9 ≤ l_i ≤ r_i ≤ 10^9), where l_i and r_i are the coordinates of the left and right borders of the i-th segment, respectively.

The segments are given in an arbitrary order.

It is guaranteed that the sum of n over all test cases does not exceed 2⋅10^5.

Output

Print t integers — the answers to the t given test cases in the order of input. The answer is the maximum number of segments in the union of n-1 segments if you erase any of the given n segments.

Example

Input


3
4
1 4
2 3
3 6
5 7
3
5 5
5 5
5 5
6
3 3
1 1
5 5
1 5
2 2
4 4


Output


2
1
5

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
long long powmod(long long base, long long exponent, long long mod) {
  long long result = 1;
  while (exponent > 0) {
    if (exponent % 2 == 0) {
      exponent /= 2;
      base = (base * base) % mod;
    } else {
      result = (result * base) % mod;
      exponent /= 2;
      base = (base * base) % mod;
    }
  }
  return result;
}
bool decresing(long long x, long long y) { return x > y; }
long long trin(long long start, long long stop) {
  return (stop - start + 1) * (stop + start) / 2;
}
bool sortvectorf(pair<long long, long long> a, pair<long long, long long> b) {
  return ((a.first > b.first) || (a.first == b.first && a.second > b.second));
}
bool sortvectordiv(pair<long long, long long> a, pair<long long, long long> b) {
  return a.first * b.second > b.first * a.second;
}
bool sortvectorfv(pair<long long, long long> a, pair<long long, long long> b) {
  return ((a.first > b.first) || (a.first == b.first && a.second < b.second));
}
bool sortvectors(pair<long long, long long> a, pair<long long, long long> b) {
  return ((a.second > b.second) || (a.second == b.second && a.first > b.first));
}
bool negasortvectorf(pair<long long, long long> a,
                     pair<long long, long long> b) {
  return ((a.first < b.first) || (a.first == b.first && a.second < b.second));
}
bool negasortvectors(pair<long long, long long> a,
                     pair<long long, long long> b) {
  return ((a.second < b.second) || (a.second == b.second && a.first < b.first));
}
vector<vector<long long>> findPermutationsI(vector<long long>& a) {
  sort(a.begin(), a.end());
  vector<vector<long long>> sol;
  do {
    sol.push_back(a);
  } while (next_permutation(a.begin(), a.end()));
  return sol;
}
vector<vector<string>> findPermutationsS(vector<string>& a) {
  sort(a.begin(), a.end());
  vector<vector<string>> sol;
  do {
    sol.push_back(a);
  } while (next_permutation(a.begin(), a.end()));
  return sol;
}
long long gcd(long long a, long long b) {
  if (a == 0) {
    return b;
  }
  if (b == 0) {
    return a;
  }
  return gcd(b % a, a);
}
bool isprime(long long n) {
  for (long long i = 2; i < n; i += 1) {
    if (i * i > n) {
      break;
    }
    if ((n / i) * i == n) {
      return false;
    }
  }
  return true;
}
long long fdivisor(long long n, long long fro) {
  for (long long i = 1; i < n + 1; i += 1) {
    if ((n / i) * i == n && i >= fro) {
      return i;
    }
  }
  return -1;
}
vector<long long> divlist(long long n) {
  vector<long long> curr;
  for (long long i = 2; i < n; i += 1) {
    if ((long long)i * i > n) {
      break;
    }
    if ((n / i) * i == n) {
      curr.push_back(i);
      curr.push_back(n / i);
    }
    if ((long long)i * i == n) {
      curr.pop_back();
    }
  }
  sort(curr.begin(), curr.end());
  return curr;
}
long long countdivisors(long long n, long long divd, long long rem) {
  vector<long long> divs = divlist(n);
  long long tot = 0;
  for (long long i = 0; i < divs.size(); i += 1) {
    if (divs[i] % divd == rem) {
      tot++;
    }
  }
  if (n % divd == rem) {
    tot++;
  }
  return tot;
}
long long digsum(long long num) {
  long long cr = 0;
  while (num > 0) {
    cr += num % 10;
    num /= 10;
  }
  return cr;
}
long long modInverse(long long a, long long b) {
  long long m = b;
  long long y = 0, x = 1;
  while (a > 1) {
    long long q = a / m;
    long long t = m;
    m = a % m, a = t;
    t = y;
    y = x - q * y;
    x = t;
  }
  if (x < 0) {
    x += b;
  }
  return x;
}
long long azeret(long long num, long long mod) {
  long long sil = 1;
  while (num > 1) {
    sil *= num;
    sil %= mod;
    num--;
  }
  return sil;
}
long long moddiv(long long to, long long by, long long mod) {
  to %= mod;
  while (to % by != 0) {
    to += mod;
    if (to > (by + 1) * mod) {
      return -1;
    }
  }
  return (to / by) % mod;
}
class node {
 public:
  int data1;
  int data2;
  node* nxt;
  node* bef;
  node(int dat1, int dat2, node* bif) {
    this->nxt = NULL;
    this->bef = bif;
    this->bef->nxt = this;
    this->data1 = dat1;
    this->data2 = dat2;
  }
  node(int dat1, int dat2) {
    this->nxt = NULL;
    this->bef = NULL;
    this->data1 = dat1;
    this->data2 = dat2;
  }
  node() {
    this->nxt = NULL;
    this->bef = NULL;
    this->data1 = 0;
    this->data2 = 0;
  }
  void remove() {
    this->bef->nxt = this->nxt;
    if (this->nxt != NULL) {
      this->nxt->bef = this->bef;
    }
  }
  void push(int dat1, int dat2) {
    node* next = this->nxt;
    node* curr = new node(dat1, dat2, this);
    curr->nxt = next;
    next->bef = curr;
  }
};
vector<int> subsum(vector<int> items, int limit) {
  vector<vector<short>> table(items.size() + 1, vector<short>(limit + 1));
  for (long long j = 1; j < items.size() + 1; j += 1) {
    short wt = items[j - 1];
    short val = wt;
    for (int w = 1; w < limit + 1; w++) {
      if (wt > w) {
        table[j][w] = table[j - 1][w];
      } else {
        table[j][w] = max(table[j - 1][w], (short)(table[j - 1][w - wt] + val));
      }
    }
  }
  vector<int> result;
  int w = limit;
  for (int j = items.size(); j > 0; j--) {
    bool was_added = table[j][w] != table[j - 1][w];
    if (was_added) {
      int wt = items[j - 1];
      int val = wt;
      result.push_back(j - 1);
      w -= wt;
    }
  }
  sort(result.begin(), result.end());
  return result;
}
void flush() { cout.flush(); }
bool by_first(pair<pair<long long, long long>, pair<long long, long long>> a,
              pair<pair<long long, long long>, pair<long long, long long>> b) {
  return a.first.first < b.first.first;
}
bool ff_fs(pair<pair<long long, bool>, long long> a,
           pair<pair<long long, bool>, long long> b) {
  return a.first.first < b.first.first ||
         (a.first.first == b.first.first && a.first.second && !b.first.second);
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  long long t;
  cin >> t;
  for (long long j = 0; j < t; j += 1) {
    long long n;
    cin >> n;
    vector<pair<pair<long long, bool>, long long>> crocs(2 * n);
    for (long long i = 0; i < n; i += 1) {
      cin >> crocs[2 * i].first.first;
      crocs[2 * i].first.second = true;
      crocs[2 * i].second = i;
      cin >> crocs[2 * i + 1].first.first;
      crocs[2 * i + 1].first.second = false;
      crocs[2 * i + 1].second = i;
    }
    sort(crocs.begin(), crocs.end(), ff_fs);
    vector<long long> points(n);
    long long cnt = 0, segs = 0;
    set<long long> live;
    for (long long i = 0; i < 2 * n; i += 1) {
      if (crocs[i].first.second) {
        cnt++;
        live.insert(crocs[i].second);
        continue;
      }
      if (cnt == 1) {
        points[crocs[i].second]--;
        segs++;
      }
      cnt--;
      live.erase(crocs[i].second);
      if (cnt == 1) {
        points[*live.begin()]++;
      }
    }
    long long mxp = -2;
    for (long long i = 0; i < n; i += 1) {
      if (points[i] > mxp) {
        mxp = points[i];
      }
    }
    cout << segs + mxp << endl;
  }
  return 0;
}

```