#include <bits/stdc++.h>
int a[400005], b[800005];
struct Segment {
  int l, r;
  bool operator<(const Segment& other) const { return l < other.l; }
};
Segment seg[200005];
long long diff[800005], record[800005];
struct SegmentT {
  int l, r;
  int lbit, rbit;
  int count;
  SegmentT() { l = r = lbit = rbit = count = 0; }
};
SegmentT t[3200005];
int preWork(int n) {
  std::sort(a + 1, a + 1 + n);
  int p = 1, size = 0;
  while (p <= n) {
    int np = p;
    while (np + 1 <= n && a[np + 1] == a[p]) np++;
    b[++size] = a[p];
    b[++size] = a[p];
    p = np + 1;
  }
  return size;
}
int getLeft(int u, int n) {
  int L = 1, R = n;
  int res = -1;
  while (L <= R) {
    int M = (L + R) / 2;
    if (b[M] >= u) {
      res = M;
      R = M - 1;
    } else
      L = M + 1;
  }
  return res;
}
int max(int a, int b) { return a > b ? a : b; }
int getUnion(int n) {
  std::sort(seg + 1, seg + 1 + n);
  int p = 1, count = 0;
  int inter = 0;
  while (p <= n) {
    count++;
    int np = p, right = seg[p].r;
    while (np + 1 <= n && seg[np + 1].l <= right) {
      inter = 1;
      np++;
      right = max(right, seg[np].r);
    }
    p = np + 1;
  }
  if (inter == 0)
    return -count;
  else
    return count;
}
int getSegment(int l, int r) {
  int p = l, count = 0;
  while (p <= r) {
    if (record[p] != 1)
      p++;
    else {
      count++;
      int np = p;
      while (np + 1 <= r && record[np + 1] == record[p]) {
        np++;
      }
      p = np + 1;
    }
  }
  return count;
}
SegmentT merge(SegmentT& a, SegmentT& b) {
  SegmentT res;
  res.l = a.l, res.r = b.r;
  res.lbit = a.lbit, res.rbit = b.rbit;
  res.count = a.count + b.count;
  if (a.rbit == 0 && b.lbit == 0) res.count--;
  return res;
}
void build(int p, int l, int r) {
  t[p].l = l, t[p].r = r;
  if (l == r) {
    t[p].lbit = t[p].rbit = (record[l] != 1);
    t[p].count = record[l] == 1;
  } else {
    int m = (l + r) / 2;
    build(2 * p, l, m);
    build(2 * p + 1, m + 1, r);
    t[p] = merge(t[2 * p], t[2 * p + 1]);
  }
}
SegmentT ask(int p, int l, int r) {
  if (l <= t[p].l && r >= t[p].r)
    return t[p];
  else {
    int m = (t[p].l + t[p].r) / 2;
    if (r <= m)
      return ask(2 * p, l, r);
    else if (l > m)
      return ask(2 * p + 1, l, r);
    else {
      SegmentT a = ask(2 * p, l, r);
      SegmentT b = ask(2 * p + 1, l, r);
      return merge(a, b);
    }
  }
}
int main() {
  int T;
  scanf("%d", &T);
  while (T--) {
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
      scanf("%d%d", &seg[i].l, &seg[i].r);
      a[2 * i - 1] = seg[i].l, a[2 * i] = seg[i].r;
    }
    int size = preWork(2 * n);
    for (int i = 1; i <= size; i++) diff[i] = 0;
    for (int i = 1; i <= n; i++) {
      int l = getLeft(seg[i].l, size), r = getLeft(seg[i].r, size);
      diff[l]++, diff[r + 1]--;
    }
    long long add = 0;
    for (int i = 1; i <= size; i++) {
      add += diff[i];
      record[i] = add;
    }
    build(1, 1, size);
    int total = getUnion(n);
    int ans = total;
    if (total < 0)
      printf("%d\n", -1 - total);
    else {
      for (int i = 1; i <= n; i++) {
        int l = getLeft(seg[i].l, size), r = getLeft(seg[i].r, size);
        SegmentT res = ask(1, l, r);
        if (res.lbit == 0) res.count--;
        if (res.rbit == 0) res.count--;
        ans = max(ans, total + res.count);
      }
      printf("%d\n", ans);
    }
  }
  return 0;
}

### Prompt

Your task is to create a CPP solution 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>
int a[400005], b[800005];
struct Segment {
  int l, r;
  bool operator<(const Segment& other) const { return l < other.l; }
};
Segment seg[200005];
long long diff[800005], record[800005];
struct SegmentT {
  int l, r;
  int lbit, rbit;
  int count;
  SegmentT() { l = r = lbit = rbit = count = 0; }
};
SegmentT t[3200005];
int preWork(int n) {
  std::sort(a + 1, a + 1 + n);
  int p = 1, size = 0;
  while (p <= n) {
    int np = p;
    while (np + 1 <= n && a[np + 1] == a[p]) np++;
    b[++size] = a[p];
    b[++size] = a[p];
    p = np + 1;
  }
  return size;
}
int getLeft(int u, int n) {
  int L = 1, R = n;
  int res = -1;
  while (L <= R) {
    int M = (L + R) / 2;
    if (b[M] >= u) {
      res = M;
      R = M - 1;
    } else
      L = M + 1;
  }
  return res;
}
int max(int a, int b) { return a > b ? a : b; }
int getUnion(int n) {
  std::sort(seg + 1, seg + 1 + n);
  int p = 1, count = 0;
  int inter = 0;
  while (p <= n) {
    count++;
    int np = p, right = seg[p].r;
    while (np + 1 <= n && seg[np + 1].l <= right) {
      inter = 1;
      np++;
      right = max(right, seg[np].r);
    }
    p = np + 1;
  }
  if (inter == 0)
    return -count;
  else
    return count;
}
int getSegment(int l, int r) {
  int p = l, count = 0;
  while (p <= r) {
    if (record[p] != 1)
      p++;
    else {
      count++;
      int np = p;
      while (np + 1 <= r && record[np + 1] == record[p]) {
        np++;
      }
      p = np + 1;
    }
  }
  return count;
}
SegmentT merge(SegmentT& a, SegmentT& b) {
  SegmentT res;
  res.l = a.l, res.r = b.r;
  res.lbit = a.lbit, res.rbit = b.rbit;
  res.count = a.count + b.count;
  if (a.rbit == 0 && b.lbit == 0) res.count--;
  return res;
}
void build(int p, int l, int r) {
  t[p].l = l, t[p].r = r;
  if (l == r) {
    t[p].lbit = t[p].rbit = (record[l] != 1);
    t[p].count = record[l] == 1;
  } else {
    int m = (l + r) / 2;
    build(2 * p, l, m);
    build(2 * p + 1, m + 1, r);
    t[p] = merge(t[2 * p], t[2 * p + 1]);
  }
}
SegmentT ask(int p, int l, int r) {
  if (l <= t[p].l && r >= t[p].r)
    return t[p];
  else {
    int m = (t[p].l + t[p].r) / 2;
    if (r <= m)
      return ask(2 * p, l, r);
    else if (l > m)
      return ask(2 * p + 1, l, r);
    else {
      SegmentT a = ask(2 * p, l, r);
      SegmentT b = ask(2 * p + 1, l, r);
      return merge(a, b);
    }
  }
}
int main() {
  int T;
  scanf("%d", &T);
  while (T--) {
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
      scanf("%d%d", &seg[i].l, &seg[i].r);
      a[2 * i - 1] = seg[i].l, a[2 * i] = seg[i].r;
    }
    int size = preWork(2 * n);
    for (int i = 1; i <= size; i++) diff[i] = 0;
    for (int i = 1; i <= n; i++) {
      int l = getLeft(seg[i].l, size), r = getLeft(seg[i].r, size);
      diff[l]++, diff[r + 1]--;
    }
    long long add = 0;
    for (int i = 1; i <= size; i++) {
      add += diff[i];
      record[i] = add;
    }
    build(1, 1, size);
    int total = getUnion(n);
    int ans = total;
    if (total < 0)
      printf("%d\n", -1 - total);
    else {
      for (int i = 1; i <= n; i++) {
        int l = getLeft(seg[i].l, size), r = getLeft(seg[i].r, size);
        SegmentT res = ask(1, l, r);
        if (res.lbit == 0) res.count--;
        if (res.rbit == 0) res.count--;
        ans = max(ans, total + res.count);
      }
      printf("%d\n", ans);
    }
  }
  return 0;
}

```