#include <bits/stdc++.h>
using namespace std;
template <typename T>
ostream &operator<<(ostream &os, const vector<T> &V) {
  long long N = V.size();
  if (N == 0) {
    os << '.';
    return os;
  }
  for (long long i = 0; i < N - 1; i++) {
    os << V[i] << ' ';
  }
  os << V[N - 1];
  return os;
}
template <typename T>
ostream &operator<<(ostream &os, const vector<vector<T>> &V) {
  long long N = V.size();
  for (long long i = 0; i < N - 1; i++) os << V[i] << "\n";
  os << V[N - 1];
  return os;
}
template <typename T, typename S>
ostream &operator<<(ostream &os, pair<T, S> const &P) {
  os << P.first << ' ' << P.second;
  return os;
}
template <typename T>
void Vin(vector<T> &v) {
  long long n = v.size();
  for (long long i = 0; i < n; i++) cin >> v[i];
}
long long scomb(long long n, long long r) {
  if (r < 0 || r > n) return 0;
  if ((n - r) < r) r = n - r;
  long long a = 1;
  for (long long i = n; i > n - r; --i) {
    a = a * i;
  }
  for (long long i = 1; i < r + 1; ++i) {
    a = a / i;
  }
  return a;
}
long long digit_sum(long long n) {
  long long ret = 0;
  while (n > 0) {
    ret += n % 10;
    n /= 10;
  }
  return ret;
}
long long digit(long long k, long long i) {
  string s = to_string(k);
  return s[s.size() - i] - '0';
}
template <typename T>
void press(T &v) {
  v.erase(unique((v).begin(), (v).end()), v.end());
}
long long SMALLER(vector<long long> &a, long long x) {
  return lower_bound(a.begin(), a.end(), x) - a.begin();
}
long long orSMALLER(vector<long long> &a, long long x) {
  return upper_bound(a.begin(), a.end(), x) - a.begin();
}
long long BIGGER(vector<long long> &a, long long x) {
  return a.size() - orSMALLER(a, x);
}
long long orBIGGER(vector<long long> &a, long long x) {
  return a.size() - SMALLER(a, x);
}
long long COUNT(vector<long long> &a, long long x) {
  return upper_bound((a).begin(), (a).end(), x) -
         lower_bound((a).begin(), (a).end(), x);
}
long long maxind(vector<long long> &a) {
  return max_element((a).begin(), (a).end()) - a.begin();
}
long long minind(vector<long long> &a) {
  return min_element((a).begin(), (a).end()) - a.begin();
}
template <typename T>
bool chmax(T &a, T b) {
  if (a < b) {
    a = b;
    return 1;
  }
  return 0;
}
template <typename T>
bool chmin(T &a, T b) {
  if (a > b) {
    a = b;
    return 1;
  }
  return 0;
}
const long long MOD = 1000000007;
const double EPS = 1e-10;
void init() {
  cin.tie(0);
  cout.tie(0);
  ios::sync_with_stdio(0);
  cout << fixed << setprecision(12);
}
using XX = long long;
XX INF_X() { return 3000000000000000000; }
XX ZERO_X() { return 0; }
struct edge {
  long long to;
  XX cost;
};
struct graph {
  long long N;
  vector<vector<edge>> G;
  vector<XX> dist;
  vector<long long> prever;
  graph(long long n) { init(n); }
  void init(long long n) {
    N = n;
    G.resize(N);
    dist.resize(N, INF_X());
  }
  void add_edge(long long s, long long t, XX cost) {
    edge e;
    e.to = t, e.cost = cost;
    G[s].push_back(e);
  }
  XX add(XX a, XX b) { return a + b; }
  void dijkstra(long long s) {
    for (long long i = 0; i < N; i++) dist[i] = INF_X();
    prever = vector<long long>(N, -1);
    dist[s] = ZERO_X();
    priority_queue<pair<XX, long long>, vector<pair<XX, long long>>,
                   greater<pair<XX, long long>>>
        q;
    q.push(make_pair(ZERO_X(), s));
    while (!q.empty()) {
      long long now;
      XX nowdist;
      tie(nowdist, now) = q.top();
      q.pop();
      if (dist[now] < nowdist) continue;
      for (auto e : G[now]) {
        if (dist[e.to] > add(dist[now], e.cost)) {
          prever[e.to] = now;
          dist[e.to] = add(dist[now], e.cost);
          q.push(make_pair(dist[e.to], e.to));
        }
      }
    }
  }
  bool bellman_ford(long long s) {
    for (long long i = 0; i < N; i++) {
      dist[i] = INF_X();
    }
    dist[s] = ZERO_X();
    for (long long i = 0; i < N; i++) {
      for (long long j = 0; j < N; j++) {
        for (auto e : G[j]) {
          if (dist[e.to] > add(dist[j], e.cost)) {
            dist[e.to] = add(dist[j], e.cost);
            if (i == N - 1) {
              return false;
            }
          }
        }
      }
    }
    return true;
  }
  vector<long long> get_path(long long t) {
    if (dist[t] >= 3000000000000000000 / 2) return {-1};
    vector<long long> path;
    for (; t != -1; t = prever[t]) {
      path.push_back(t);
    }
    reverse(path.begin(), path.end());
    return path;
  }
};
long long f(vector<long long> &l, vector<long long> &r, vector<long long> &c) {
  long long ret = 0;
  if (l.size() == 0) return 0;
  long long N = max(*max_element((l).begin(), (l).end()),
                    *max_element((r).begin(), (r).end())) +
                5;
  long long M = 100000;
  graph gr(N);
  for (long long i = 0; i < N - 1; i++) {
    gr.add_edge(i, i + 1, M);
  }
  for (long long i = 0; i < l.size(); i++) {
    long long co = M * (r[i] + 1 - l[i]) - c[i];
    gr.add_edge(l[i], r[i] + 1, co);
  }
  gr.dijkstra(0);
  ret = M * (N - 1) - gr.dist[N - 1];
  return ret;
}
void sol() {
  long long n;
  cin >> n;
  vector<long long> l(n), r(n), QW, ER;
  for (long long i = 0; i < n; i++) {
    cin >> l[i] >> r[i];
    QW.push_back(l[i]);
    QW.push_back(r[i]);
  }
  n++;
  l.push_back(-1);
  r.push_back(3000000000000000000);
  QW.push_back(-1);
  QW.push_back(3000000000000000000);
  sort((QW).begin(), (QW).end());
  press(QW);
  map<long long, long long> ma;
  for (long long i = 0; i < QW.size(); i++) ma[QW[i]] = i;
  for (long long i = 0; i < n; i++) {
    l[i] = ma[l[i]];
    r[i] = ma[r[i]];
  }
  map<pair<long long, long long>, long long> cost;
  vector<tuple<long long, long long, long long>> vt(n);
  for (long long i = 0; i < n; i++) {
    vt[i] = make_tuple(r[i] - l[i], l[i], r[i]);
  }
  sort((vt).begin(), (vt).end());
  long long ans;
  for (long long i = 0; i < n; i++) {
    vector<long long> L, R, C;
    long long ll = get<1>(vt[i]), rr = get<2>(vt[i]);
    for (long long j = 0; j < i; j++) {
      if (ll <= get<1>(vt[j]) && get<2>(vt[j]) <= rr) {
        L.push_back(get<1>(vt[j]));
        R.push_back(get<2>(vt[j]));
        C.push_back(cost[make_pair(get<1>(vt[j]), get<2>(vt[j]))]);
      }
    }
    long long now = f(L, R, C);
    ans = now;
    cost[make_pair(ll, rr)] = now + 1;
  }
  cout << ans << "\n";
}
signed main() {
  init();
  long long q = 1;
  cin >> q;
  while (q--) sol();
  vector<long long> L = {0, 1};
  vector<long long> R = {1, 2};
  vector<long long> C = {1, 1};
  return 0;
}

### Prompt

Your challenge is to write a CPP solution to the following problem:

You are given n segments on a coordinate axis OX. The i-th segment has borders [l_i; r_i]. All points x, for which l_i ≤ x ≤ r_i holds, belong to the i-th segment.

Your task is to choose the maximum by size (the number of segments) subset of the given set of segments such that each pair of segments in this subset either non-intersecting or one of them lies inside the other one.

Two segments [l_i; r_i] and [l_j; r_j] are non-intersecting if they have no common points. For example, segments [1; 2] and [3; 4], [1; 3] and [5; 5] are non-intersecting, while segments [1; 2] and [2; 3], [1; 2] and [2; 2] are intersecting.

The segment [l_i; r_i] lies inside the segment [l_j; r_j] if l_j ≤ l_i and r_i ≤ r_j. For example, segments [2; 2], [2, 3], [3; 4] and [2; 4] lie inside the segment [2; 4], while [2; 5] and [1; 4] are not.

You have to answer t independent test cases.

Input

The first line of the input contains one integer t (1 ≤ t ≤ 1000) — the number of test cases. Then t test cases follow.

The first line of the test case contains one integer n (1 ≤ n ≤ 3000) — the number of segments. The next n lines describe segments. The i-th segment is given as two integers l_i and r_i (1 ≤ l_i ≤ r_i ≤ 2 ⋅ 10^5), where l_i is the left border of the i-th segment and r_i is the right border of the i-th segment.

Additional constraint on the input: there are no duplicates in the list of segments.

It is guaranteed that the sum of n does not exceed 3000 (∑ n ≤ 3000).

Output

For each test case, print the answer: the maximum possible size of the subset of the given set of segments such that each pair of segments in this subset either non-intersecting or one of them lies inside the other one.

Example

Input


4
4
1 5
2 4
2 3
3 4
5
1 5
2 3
2 5
3 5
2 2
3
1 3
2 4
2 3
7
1 10
2 8
2 5
3 4
4 4
6 8
7 7


Output


3
4
2
7

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
template <typename T>
ostream &operator<<(ostream &os, const vector<T> &V) {
  long long N = V.size();
  if (N == 0) {
    os << '.';
    return os;
  }
  for (long long i = 0; i < N - 1; i++) {
    os << V[i] << ' ';
  }
  os << V[N - 1];
  return os;
}
template <typename T>
ostream &operator<<(ostream &os, const vector<vector<T>> &V) {
  long long N = V.size();
  for (long long i = 0; i < N - 1; i++) os << V[i] << "\n";
  os << V[N - 1];
  return os;
}
template <typename T, typename S>
ostream &operator<<(ostream &os, pair<T, S> const &P) {
  os << P.first << ' ' << P.second;
  return os;
}
template <typename T>
void Vin(vector<T> &v) {
  long long n = v.size();
  for (long long i = 0; i < n; i++) cin >> v[i];
}
long long scomb(long long n, long long r) {
  if (r < 0 || r > n) return 0;
  if ((n - r) < r) r = n - r;
  long long a = 1;
  for (long long i = n; i > n - r; --i) {
    a = a * i;
  }
  for (long long i = 1; i < r + 1; ++i) {
    a = a / i;
  }
  return a;
}
long long digit_sum(long long n) {
  long long ret = 0;
  while (n > 0) {
    ret += n % 10;
    n /= 10;
  }
  return ret;
}
long long digit(long long k, long long i) {
  string s = to_string(k);
  return s[s.size() - i] - '0';
}
template <typename T>
void press(T &v) {
  v.erase(unique((v).begin(), (v).end()), v.end());
}
long long SMALLER(vector<long long> &a, long long x) {
  return lower_bound(a.begin(), a.end(), x) - a.begin();
}
long long orSMALLER(vector<long long> &a, long long x) {
  return upper_bound(a.begin(), a.end(), x) - a.begin();
}
long long BIGGER(vector<long long> &a, long long x) {
  return a.size() - orSMALLER(a, x);
}
long long orBIGGER(vector<long long> &a, long long x) {
  return a.size() - SMALLER(a, x);
}
long long COUNT(vector<long long> &a, long long x) {
  return upper_bound((a).begin(), (a).end(), x) -
         lower_bound((a).begin(), (a).end(), x);
}
long long maxind(vector<long long> &a) {
  return max_element((a).begin(), (a).end()) - a.begin();
}
long long minind(vector<long long> &a) {
  return min_element((a).begin(), (a).end()) - a.begin();
}
template <typename T>
bool chmax(T &a, T b) {
  if (a < b) {
    a = b;
    return 1;
  }
  return 0;
}
template <typename T>
bool chmin(T &a, T b) {
  if (a > b) {
    a = b;
    return 1;
  }
  return 0;
}
const long long MOD = 1000000007;
const double EPS = 1e-10;
void init() {
  cin.tie(0);
  cout.tie(0);
  ios::sync_with_stdio(0);
  cout << fixed << setprecision(12);
}
using XX = long long;
XX INF_X() { return 3000000000000000000; }
XX ZERO_X() { return 0; }
struct edge {
  long long to;
  XX cost;
};
struct graph {
  long long N;
  vector<vector<edge>> G;
  vector<XX> dist;
  vector<long long> prever;
  graph(long long n) { init(n); }
  void init(long long n) {
    N = n;
    G.resize(N);
    dist.resize(N, INF_X());
  }
  void add_edge(long long s, long long t, XX cost) {
    edge e;
    e.to = t, e.cost = cost;
    G[s].push_back(e);
  }
  XX add(XX a, XX b) { return a + b; }
  void dijkstra(long long s) {
    for (long long i = 0; i < N; i++) dist[i] = INF_X();
    prever = vector<long long>(N, -1);
    dist[s] = ZERO_X();
    priority_queue<pair<XX, long long>, vector<pair<XX, long long>>,
                   greater<pair<XX, long long>>>
        q;
    q.push(make_pair(ZERO_X(), s));
    while (!q.empty()) {
      long long now;
      XX nowdist;
      tie(nowdist, now) = q.top();
      q.pop();
      if (dist[now] < nowdist) continue;
      for (auto e : G[now]) {
        if (dist[e.to] > add(dist[now], e.cost)) {
          prever[e.to] = now;
          dist[e.to] = add(dist[now], e.cost);
          q.push(make_pair(dist[e.to], e.to));
        }
      }
    }
  }
  bool bellman_ford(long long s) {
    for (long long i = 0; i < N; i++) {
      dist[i] = INF_X();
    }
    dist[s] = ZERO_X();
    for (long long i = 0; i < N; i++) {
      for (long long j = 0; j < N; j++) {
        for (auto e : G[j]) {
          if (dist[e.to] > add(dist[j], e.cost)) {
            dist[e.to] = add(dist[j], e.cost);
            if (i == N - 1) {
              return false;
            }
          }
        }
      }
    }
    return true;
  }
  vector<long long> get_path(long long t) {
    if (dist[t] >= 3000000000000000000 / 2) return {-1};
    vector<long long> path;
    for (; t != -1; t = prever[t]) {
      path.push_back(t);
    }
    reverse(path.begin(), path.end());
    return path;
  }
};
long long f(vector<long long> &l, vector<long long> &r, vector<long long> &c) {
  long long ret = 0;
  if (l.size() == 0) return 0;
  long long N = max(*max_element((l).begin(), (l).end()),
                    *max_element((r).begin(), (r).end())) +
                5;
  long long M = 100000;
  graph gr(N);
  for (long long i = 0; i < N - 1; i++) {
    gr.add_edge(i, i + 1, M);
  }
  for (long long i = 0; i < l.size(); i++) {
    long long co = M * (r[i] + 1 - l[i]) - c[i];
    gr.add_edge(l[i], r[i] + 1, co);
  }
  gr.dijkstra(0);
  ret = M * (N - 1) - gr.dist[N - 1];
  return ret;
}
void sol() {
  long long n;
  cin >> n;
  vector<long long> l(n), r(n), QW, ER;
  for (long long i = 0; i < n; i++) {
    cin >> l[i] >> r[i];
    QW.push_back(l[i]);
    QW.push_back(r[i]);
  }
  n++;
  l.push_back(-1);
  r.push_back(3000000000000000000);
  QW.push_back(-1);
  QW.push_back(3000000000000000000);
  sort((QW).begin(), (QW).end());
  press(QW);
  map<long long, long long> ma;
  for (long long i = 0; i < QW.size(); i++) ma[QW[i]] = i;
  for (long long i = 0; i < n; i++) {
    l[i] = ma[l[i]];
    r[i] = ma[r[i]];
  }
  map<pair<long long, long long>, long long> cost;
  vector<tuple<long long, long long, long long>> vt(n);
  for (long long i = 0; i < n; i++) {
    vt[i] = make_tuple(r[i] - l[i], l[i], r[i]);
  }
  sort((vt).begin(), (vt).end());
  long long ans;
  for (long long i = 0; i < n; i++) {
    vector<long long> L, R, C;
    long long ll = get<1>(vt[i]), rr = get<2>(vt[i]);
    for (long long j = 0; j < i; j++) {
      if (ll <= get<1>(vt[j]) && get<2>(vt[j]) <= rr) {
        L.push_back(get<1>(vt[j]));
        R.push_back(get<2>(vt[j]));
        C.push_back(cost[make_pair(get<1>(vt[j]), get<2>(vt[j]))]);
      }
    }
    long long now = f(L, R, C);
    ans = now;
    cost[make_pair(ll, rr)] = now + 1;
  }
  cout << ans << "\n";
}
signed main() {
  init();
  long long q = 1;
  cin >> q;
  while (q--) sol();
  vector<long long> L = {0, 1};
  vector<long long> R = {1, 2};
  vector<long long> C = {1, 1};
  return 0;
}

```