#include <bits/stdc++.h>
#pragma GCC optimize(2)
const int inf = 0x3f3f3f3f, Inf = 0x7fffffff;
const long long INF = 0x7fffffffffffffff;
const double eps = 1e-8;
unsigned int seed = 19260817;
const unsigned int _RAND_MAX_ = 4294967295u;
__inline__ __attribute__((always_inline)) unsigned int Rand() {
  return seed = seed * 998244353u + 1000000007u;
}
template <typename _Tp>
_Tp gcd(const _Tp &a, const _Tp &b) {
  return (!b) ? a : gcd(b, a % b);
}
template <typename _Tp>
__inline__ __attribute__((always_inline)) _Tp abs(const _Tp &a) {
  return a > 0 ? a : -a;
}
template <typename _Tp>
__inline__ __attribute__((always_inline)) _Tp max(const _Tp &a, const _Tp &b) {
  return a < b ? b : a;
}
template <typename _Tp>
__inline__ __attribute__((always_inline)) _Tp min(const _Tp &a, const _Tp &b) {
  return a < b ? a : b;
}
template <typename _Tp>
__inline__ __attribute__((always_inline)) void chmax(_Tp &a, const _Tp &b) {
  (a < b) && (a = b);
}
template <typename _Tp>
__inline__ __attribute__((always_inline)) void chmin(_Tp &a, const _Tp &b) {
  (a > b) && (a = b);
}
template <typename _Tp>
__inline__ __attribute__((always_inline)) bool _cmp(const _Tp &a,
                                                    const _Tp &b) {
  return abs(a - b) <= eps;
}
template <typename _Tp>
__inline__ __attribute__((always_inline)) void read(_Tp &x) {
  register char ch(getchar());
  bool f(false);
  while (ch < 48 || ch > 57) f |= ch == 45, ch = getchar();
  x = ch & 15, ch = getchar();
  while (ch >= 48 && ch <= 57)
    x = (((x << 2) + x) << 1) + (ch & 15), ch = getchar();
  if (f) x = -x;
}
template <typename _Tp, typename... Args>
__inline__ __attribute__((always_inline)) void read(_Tp &t, Args &...args) {
  read(t);
  read(args...);
}
__inline__ __attribute__((always_inline)) int read_str(char *s) {
  register char ch(getchar());
  while (ch == ' ' || ch == '\r' || ch == '\n') ch = getchar();
  register char *tar = s;
  *tar = ch, ch = getchar();
  while (ch != ' ' && ch != '\r' && ch != '\n' && ch != EOF)
    *(++tar) = ch, ch = getchar();
  return tar - s + 1;
}
const int N = 1200005;
struct node {
  bool l, r;
  int ans;
  __inline__ __attribute__((always_inline)) node operator+(
      const node &o) const {
    return (node){l, o.r, ans + o.ans - (r == o.l)};
  }
};
int L[N], R[N];
int t[N];
int a[N];
struct seg_tr {
  struct Node {
    int ls, rs;
    node val1, val2;
    bool tag;
  } f[N << 1];
  int node_cnt;
  __inline__ __attribute__((always_inline)) void PushUp(int x) {
    f[x].val1 = f[f[x].ls].val1 + f[f[x].rs].val1;
    f[x].val2 = f[f[x].ls].val2 + f[f[x].rs].val2;
  }
  int build(int l, int r) {
    int cur = ++node_cnt;
    f[cur].tag = 0;
    if (l == r) {
      f[cur].ls = f[cur].rs = 0;
      f[cur].val1 = (node){a[l] == 0, a[l] == 0, 1};
      f[cur].val2 = (node){a[l] == 1, a[l] == 1, 1};
      return cur;
    }
    int mid = (l + r) >> 1;
    f[cur].ls = build(l, mid);
    f[cur].rs = build(mid + 1, r);
    PushUp(cur);
    return cur;
  }
  __inline__ __attribute__((always_inline)) void upd(int cur) {
    f[cur].tag ^= 1;
    std::swap(f[cur].val1, f[cur].val2);
  }
  __inline__ __attribute__((always_inline)) void PushDown(int cur) {
    if (f[cur].tag) {
      upd(f[cur].ls);
      upd(f[cur].rs);
      f[cur].tag = 0;
    }
  }
  void Update(int L, int R, int l, int r, int cur) {
    if (L <= l && r <= R) {
      upd(cur);
      return;
    }
    PushDown(cur);
    int mid = (l + r) >> 1;
    if (L <= mid) Update(L, R, l, mid, f[cur].ls);
    if (R > mid) Update(L, R, mid + 1, r, f[cur].rs);
    PushUp(cur);
  }
  __inline__ __attribute__((always_inline)) int Query() {
    return f[1].val1.ans;
  }
} tr;
void MAIN() {
  tr.node_cnt = 0;
  int n;
  read(n);
  int len = 0;
  for (int i = 1; i <= n; ++i) {
    read(L[i], R[i]);
    t[++len] = L[i];
    t[++len] = R[i];
  }
  std::sort(t + 1, t + len + 1);
  len = std::unique(t + 1, t + len + 1) - t - 1;
  memset(a, 0, 8 * (len + 2));
  for (int i = 1; i <= n; ++i) {
    L[i] = std::lower_bound(t + 1, t + len + 1, L[i]) - t;
    R[i] = std::lower_bound(t + 1, t + len + 1, R[i]) - t;
    L[i] <<= 1;
    R[i] <<= 1;
    ++a[L[i]];
    --a[R[i] + 1];
  }
  len <<= 1;
  for (int i = 1; i <= len; ++i) a[i] += a[i - 1];
  int root = tr.build(1, len);
  int ans = 0;
  for (int i = 1; i <= n; ++i) {
    tr.Update(L[i], R[i], 1, len, root);
    chmax(ans, tr.Query() >> 1);
    tr.Update(L[i], R[i], 1, len, root);
  }
  printf("%d\n", ans);
}
int main() {
  int _;
  read(_);
  while (_--) MAIN();
  return 0;
}

### Prompt

Develop a solution in Cpp to the problem described below:

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>
#pragma GCC optimize(2)
const int inf = 0x3f3f3f3f, Inf = 0x7fffffff;
const long long INF = 0x7fffffffffffffff;
const double eps = 1e-8;
unsigned int seed = 19260817;
const unsigned int _RAND_MAX_ = 4294967295u;
__inline__ __attribute__((always_inline)) unsigned int Rand() {
  return seed = seed * 998244353u + 1000000007u;
}
template <typename _Tp>
_Tp gcd(const _Tp &a, const _Tp &b) {
  return (!b) ? a : gcd(b, a % b);
}
template <typename _Tp>
__inline__ __attribute__((always_inline)) _Tp abs(const _Tp &a) {
  return a > 0 ? a : -a;
}
template <typename _Tp>
__inline__ __attribute__((always_inline)) _Tp max(const _Tp &a, const _Tp &b) {
  return a < b ? b : a;
}
template <typename _Tp>
__inline__ __attribute__((always_inline)) _Tp min(const _Tp &a, const _Tp &b) {
  return a < b ? a : b;
}
template <typename _Tp>
__inline__ __attribute__((always_inline)) void chmax(_Tp &a, const _Tp &b) {
  (a < b) && (a = b);
}
template <typename _Tp>
__inline__ __attribute__((always_inline)) void chmin(_Tp &a, const _Tp &b) {
  (a > b) && (a = b);
}
template <typename _Tp>
__inline__ __attribute__((always_inline)) bool _cmp(const _Tp &a,
                                                    const _Tp &b) {
  return abs(a - b) <= eps;
}
template <typename _Tp>
__inline__ __attribute__((always_inline)) void read(_Tp &x) {
  register char ch(getchar());
  bool f(false);
  while (ch < 48 || ch > 57) f |= ch == 45, ch = getchar();
  x = ch & 15, ch = getchar();
  while (ch >= 48 && ch <= 57)
    x = (((x << 2) + x) << 1) + (ch & 15), ch = getchar();
  if (f) x = -x;
}
template <typename _Tp, typename... Args>
__inline__ __attribute__((always_inline)) void read(_Tp &t, Args &...args) {
  read(t);
  read(args...);
}
__inline__ __attribute__((always_inline)) int read_str(char *s) {
  register char ch(getchar());
  while (ch == ' ' || ch == '\r' || ch == '\n') ch = getchar();
  register char *tar = s;
  *tar = ch, ch = getchar();
  while (ch != ' ' && ch != '\r' && ch != '\n' && ch != EOF)
    *(++tar) = ch, ch = getchar();
  return tar - s + 1;
}
const int N = 1200005;
struct node {
  bool l, r;
  int ans;
  __inline__ __attribute__((always_inline)) node operator+(
      const node &o) const {
    return (node){l, o.r, ans + o.ans - (r == o.l)};
  }
};
int L[N], R[N];
int t[N];
int a[N];
struct seg_tr {
  struct Node {
    int ls, rs;
    node val1, val2;
    bool tag;
  } f[N << 1];
  int node_cnt;
  __inline__ __attribute__((always_inline)) void PushUp(int x) {
    f[x].val1 = f[f[x].ls].val1 + f[f[x].rs].val1;
    f[x].val2 = f[f[x].ls].val2 + f[f[x].rs].val2;
  }
  int build(int l, int r) {
    int cur = ++node_cnt;
    f[cur].tag = 0;
    if (l == r) {
      f[cur].ls = f[cur].rs = 0;
      f[cur].val1 = (node){a[l] == 0, a[l] == 0, 1};
      f[cur].val2 = (node){a[l] == 1, a[l] == 1, 1};
      return cur;
    }
    int mid = (l + r) >> 1;
    f[cur].ls = build(l, mid);
    f[cur].rs = build(mid + 1, r);
    PushUp(cur);
    return cur;
  }
  __inline__ __attribute__((always_inline)) void upd(int cur) {
    f[cur].tag ^= 1;
    std::swap(f[cur].val1, f[cur].val2);
  }
  __inline__ __attribute__((always_inline)) void PushDown(int cur) {
    if (f[cur].tag) {
      upd(f[cur].ls);
      upd(f[cur].rs);
      f[cur].tag = 0;
    }
  }
  void Update(int L, int R, int l, int r, int cur) {
    if (L <= l && r <= R) {
      upd(cur);
      return;
    }
    PushDown(cur);
    int mid = (l + r) >> 1;
    if (L <= mid) Update(L, R, l, mid, f[cur].ls);
    if (R > mid) Update(L, R, mid + 1, r, f[cur].rs);
    PushUp(cur);
  }
  __inline__ __attribute__((always_inline)) int Query() {
    return f[1].val1.ans;
  }
} tr;
void MAIN() {
  tr.node_cnt = 0;
  int n;
  read(n);
  int len = 0;
  for (int i = 1; i <= n; ++i) {
    read(L[i], R[i]);
    t[++len] = L[i];
    t[++len] = R[i];
  }
  std::sort(t + 1, t + len + 1);
  len = std::unique(t + 1, t + len + 1) - t - 1;
  memset(a, 0, 8 * (len + 2));
  for (int i = 1; i <= n; ++i) {
    L[i] = std::lower_bound(t + 1, t + len + 1, L[i]) - t;
    R[i] = std::lower_bound(t + 1, t + len + 1, R[i]) - t;
    L[i] <<= 1;
    R[i] <<= 1;
    ++a[L[i]];
    --a[R[i] + 1];
  }
  len <<= 1;
  for (int i = 1; i <= len; ++i) a[i] += a[i - 1];
  int root = tr.build(1, len);
  int ans = 0;
  for (int i = 1; i <= n; ++i) {
    tr.Update(L[i], R[i], 1, len, root);
    chmax(ans, tr.Query() >> 1);
    tr.Update(L[i], R[i], 1, len, root);
  }
  printf("%d\n", ans);
}
int main() {
  int _;
  read(_);
  while (_--) MAIN();
  return 0;
}

```