#include <bits/stdc++.h>
inline long long sbt(long long x) { return __builtin_popcount(x); }
using namespace std;
template <typename Arg1>
void __f(const char* name, Arg1&& arg1) {
  cout << name << " : " << arg1 << std::endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args) {
  const char* comma = strchr(names + 1, ',');
  cout.write(names, comma - names) << " : " << arg1 << " | ";
  __f(comma + 1, args...);
}
bool ok;
long long n, pichla, ek, x, g, bd, m1, m2, curr, place22, place4, nb, maxi,
    chosen1, chosen2, chosen3, inplace, xs, l, r, res2, mdf, k, K, sabka_baap;
multiset<pair<long long, pair<long long, long long>>> events;
long long res, h, a[100013];
string s[100013], ss[100013];
set<long long> segments;
vector<pair<long long, long long>> v;
vector<long long> buff;
bool cmp(pair<long long, pair<long long, pair<long long, long long>>> x,
         pair<long long, pair<long long, pair<long long, long long>>> y) {
  return x.second.first < y.second.first;
}
inline long long mul(long long a, long long b, long long m = 1000000007) {
  return (a * b) % m;
}
inline long long add(long long a, long long b, long long m = 1000000007) {
  return (a + b) % m;
}
inline long long sub(long long a, long long b, long long m = 1000000007) {
  return (a - b + m) % m;
}
long long fastpow(long long a, long long b) {
  long long res = 1;
  while (b > 0) {
    if (b & 1) res = mul(res, a);
    a = mul(a, a);
    b >>= 1;
  }
  return res;
}
long long modinv(long long a) { return fastpow(a, 1000000007 - 2); }
int32_t main() {
  long long t;
  cin >> t;
  while (t--) {
    events.clear();
    segments.clear();
    v.clear();
    cin >> n;
    for (long long i = 1; i <= n; i++) {
      cin >> l >> r;
      v.push_back(make_pair(l, r));
      events.insert(make_pair(l, make_pair(0, i)));
      events.insert(make_pair(r, make_pair(1, i)));
    }
    sort(v.begin(), v.end());
    long long spread = v[0].second;
    pichla = v[0].first;
    long long st = 1;
    res = 1;
    while (st < n) {
      if (v[st].first <= spread) {
        spread = max(spread, v[st].second);
      } else {
        res++;
        spread = v[st].second;
        pichla = v[st].first;
      }
      st++;
    }
    bool lft_grp = 1;
    buff.assign(n + 1, 0);
    for (auto event : events) {
      bool is_end = event.second.first;
      long long curr = event.first;
      long long i = event.second.second;
      if (is_end) {
        segments.erase(segments.find(i));
        if (!segments.size()) {
          lft_grp = 1;
        }
      } else {
        if ((segments.size() == 1) && !lft_grp) {
          buff[*segments.begin()]++;
        }
        segments.insert(i);
        lft_grp = (lft_grp & (segments.size() == 1));
      }
    }
    cout << min(n - 1, res + (*max_element(buff.begin(), buff.end()))) << endl;
  }
  return 0;
}

### Prompt

Construct a cpp code solution to the problem outlined:

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>
inline long long sbt(long long x) { return __builtin_popcount(x); }
using namespace std;
template <typename Arg1>
void __f(const char* name, Arg1&& arg1) {
  cout << name << " : " << arg1 << std::endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args) {
  const char* comma = strchr(names + 1, ',');
  cout.write(names, comma - names) << " : " << arg1 << " | ";
  __f(comma + 1, args...);
}
bool ok;
long long n, pichla, ek, x, g, bd, m1, m2, curr, place22, place4, nb, maxi,
    chosen1, chosen2, chosen3, inplace, xs, l, r, res2, mdf, k, K, sabka_baap;
multiset<pair<long long, pair<long long, long long>>> events;
long long res, h, a[100013];
string s[100013], ss[100013];
set<long long> segments;
vector<pair<long long, long long>> v;
vector<long long> buff;
bool cmp(pair<long long, pair<long long, pair<long long, long long>>> x,
         pair<long long, pair<long long, pair<long long, long long>>> y) {
  return x.second.first < y.second.first;
}
inline long long mul(long long a, long long b, long long m = 1000000007) {
  return (a * b) % m;
}
inline long long add(long long a, long long b, long long m = 1000000007) {
  return (a + b) % m;
}
inline long long sub(long long a, long long b, long long m = 1000000007) {
  return (a - b + m) % m;
}
long long fastpow(long long a, long long b) {
  long long res = 1;
  while (b > 0) {
    if (b & 1) res = mul(res, a);
    a = mul(a, a);
    b >>= 1;
  }
  return res;
}
long long modinv(long long a) { return fastpow(a, 1000000007 - 2); }
int32_t main() {
  long long t;
  cin >> t;
  while (t--) {
    events.clear();
    segments.clear();
    v.clear();
    cin >> n;
    for (long long i = 1; i <= n; i++) {
      cin >> l >> r;
      v.push_back(make_pair(l, r));
      events.insert(make_pair(l, make_pair(0, i)));
      events.insert(make_pair(r, make_pair(1, i)));
    }
    sort(v.begin(), v.end());
    long long spread = v[0].second;
    pichla = v[0].first;
    long long st = 1;
    res = 1;
    while (st < n) {
      if (v[st].first <= spread) {
        spread = max(spread, v[st].second);
      } else {
        res++;
        spread = v[st].second;
        pichla = v[st].first;
      }
      st++;
    }
    bool lft_grp = 1;
    buff.assign(n + 1, 0);
    for (auto event : events) {
      bool is_end = event.second.first;
      long long curr = event.first;
      long long i = event.second.second;
      if (is_end) {
        segments.erase(segments.find(i));
        if (!segments.size()) {
          lft_grp = 1;
        }
      } else {
        if ((segments.size() == 1) && !lft_grp) {
          buff[*segments.begin()]++;
        }
        segments.insert(i);
        lft_grp = (lft_grp & (segments.size() == 1));
      }
    }
    cout << min(n - 1, res + (*max_element(buff.begin(), buff.end()))) << endl;
  }
  return 0;
}

```