#include <bits/stdc++.h>
using namespace std;
mt19937 bruh(chrono::steady_clock::now().time_since_epoch().count());
mt19937_64 rofl(chrono::steady_clock::now().time_since_epoch().count());
const int N = 3e6 + 200;
const int M = 3e6 + 200;
const int mod = 0;
const int inf = 2e9 + 3;
const long long INF = 1e18;
const int dx[4] = {1, -1, 0, 0};
const int dy[4] = {0, 0, -1, 1};
void files() {
  freopen(".in", "r", stdin);
  freopen(".out", "w", stdout);
}
int T, n, l[N], r[N], mx, add[N];
vector<int> e;
struct node {
  pair<int, int> t[M];
  pair<int, int> merge(pair<int, int> a, pair<int, int> b) {
    if (a.first == b.first)
      a.second += b.second;
    else
      a = min(a, b);
    return a;
  }
  void build(int v = 1, int tl = 1, int tr = mx) {
    if (tl == tr) {
      t[v] = {add[tl], 1};
      return;
    }
    int tm = tl + tr >> 1;
    build(v * 2, tl, tm);
    build(v * 2 + 1, tm + 1, tr);
    t[v] = merge(t[v * 2], t[v * 2 + 1]);
  }
  pair<int, int> get(int l, int r, int v = 1, int tl = 1, int tr = mx) {
    if (l <= tl && tr <= r) return t[v];
    if (tr < l || r < tl) return {inf, 0};
    int tm = tl + tr >> 1;
    return merge(get(l, r, v * 2, tl, tm), get(l, r, v * 2 + 1, tm + 1, tr));
  }
} t;
int main() {
  scanf("%d", &T);
  while (T--) {
    e.clear();
    mx = 1;
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
      scanf("%d %d", &l[i], &r[i]);
      e.push_back(l[i]), e.push_back(r[i]);
    }
    sort(e.begin(), e.end());
    e.erase(unique(e.begin(), e.end()), e.end());
    for (int i = 1; i <= n; ++i) {
      l[i] = lower_bound(e.begin(), e.end(), l[i]) - e.begin() + 1;
      r[i] = lower_bound(e.begin(), e.end(), r[i]) - e.begin() + 1;
      l[i] = l[i] * 2 - 1;
      r[i] = r[i] * 2 - 1;
      mx = max(mx, r[i]);
    }
    int meme = 1;
    for (int i = 1; i <= mx; ++i) add[i] = 0;
    for (int i = 1; i <= n; ++i) add[l[i]]++, add[r[i] + 1]--;
    for (int i = 1; i <= mx; ++i) {
      add[i] += add[i - 1];
      meme += (add[i] == 0);
    }
    t.build();
    int ans = -1;
    int ret = 0;
    pair<int, int> lmao = t.get(1, mx);
    for (int i = 1; i <= n; ++i) {
      pair<int, int> cnt = t.get(l[i], r[i]);
      if (cnt.first == 1) {
        if (cnt.second == r[i] - l[i] + 1)
          ret = -1;
        else {
          if (add[l[i]] == 1) l[i] += 2;
          if (add[r[i]] == 1) r[i] -= 2;
          pair<int, int> cnt = t.get(l[i], r[i]);
          if (cnt.first == 1)
            ret = cnt.second;
          else
            ret = 0;
        }
      } else
        ret = 0;
      ans = max(ans, ret);
    }
    printf("%d\n", ans + meme);
  }
}

### Prompt

Please create a solution in Cpp to 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;
mt19937 bruh(chrono::steady_clock::now().time_since_epoch().count());
mt19937_64 rofl(chrono::steady_clock::now().time_since_epoch().count());
const int N = 3e6 + 200;
const int M = 3e6 + 200;
const int mod = 0;
const int inf = 2e9 + 3;
const long long INF = 1e18;
const int dx[4] = {1, -1, 0, 0};
const int dy[4] = {0, 0, -1, 1};
void files() {
  freopen(".in", "r", stdin);
  freopen(".out", "w", stdout);
}
int T, n, l[N], r[N], mx, add[N];
vector<int> e;
struct node {
  pair<int, int> t[M];
  pair<int, int> merge(pair<int, int> a, pair<int, int> b) {
    if (a.first == b.first)
      a.second += b.second;
    else
      a = min(a, b);
    return a;
  }
  void build(int v = 1, int tl = 1, int tr = mx) {
    if (tl == tr) {
      t[v] = {add[tl], 1};
      return;
    }
    int tm = tl + tr >> 1;
    build(v * 2, tl, tm);
    build(v * 2 + 1, tm + 1, tr);
    t[v] = merge(t[v * 2], t[v * 2 + 1]);
  }
  pair<int, int> get(int l, int r, int v = 1, int tl = 1, int tr = mx) {
    if (l <= tl && tr <= r) return t[v];
    if (tr < l || r < tl) return {inf, 0};
    int tm = tl + tr >> 1;
    return merge(get(l, r, v * 2, tl, tm), get(l, r, v * 2 + 1, tm + 1, tr));
  }
} t;
int main() {
  scanf("%d", &T);
  while (T--) {
    e.clear();
    mx = 1;
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
      scanf("%d %d", &l[i], &r[i]);
      e.push_back(l[i]), e.push_back(r[i]);
    }
    sort(e.begin(), e.end());
    e.erase(unique(e.begin(), e.end()), e.end());
    for (int i = 1; i <= n; ++i) {
      l[i] = lower_bound(e.begin(), e.end(), l[i]) - e.begin() + 1;
      r[i] = lower_bound(e.begin(), e.end(), r[i]) - e.begin() + 1;
      l[i] = l[i] * 2 - 1;
      r[i] = r[i] * 2 - 1;
      mx = max(mx, r[i]);
    }
    int meme = 1;
    for (int i = 1; i <= mx; ++i) add[i] = 0;
    for (int i = 1; i <= n; ++i) add[l[i]]++, add[r[i] + 1]--;
    for (int i = 1; i <= mx; ++i) {
      add[i] += add[i - 1];
      meme += (add[i] == 0);
    }
    t.build();
    int ans = -1;
    int ret = 0;
    pair<int, int> lmao = t.get(1, mx);
    for (int i = 1; i <= n; ++i) {
      pair<int, int> cnt = t.get(l[i], r[i]);
      if (cnt.first == 1) {
        if (cnt.second == r[i] - l[i] + 1)
          ret = -1;
        else {
          if (add[l[i]] == 1) l[i] += 2;
          if (add[r[i]] == 1) r[i] -= 2;
          pair<int, int> cnt = t.get(l[i], r[i]);
          if (cnt.first == 1)
            ret = cnt.second;
          else
            ret = 0;
        }
      } else
        ret = 0;
      ans = max(ans, ret);
    }
    printf("%d\n", ans + meme);
  }
}

```