LA5845.cpp

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <map>
#include <set>
#include <sstream>
#include <iomanip>
#include <cmath>
#include <bitset>
#include <assert.h>

using namespace std;
typedef long long llong;
typedef set<int>::iterator ssii;

#define Cmp(a, b) memcmp(a, b, sizeof(b))
#define Cpy(a, b) memcpy(a, b, sizeof(a))
#define Set(a, v) memset(a, v, sizeof(a))
#define debug(x) cout << #x << ": " << x << endl
#define _forS(i, l, r) for(set<int>::iterator i = (l); i != (r); i++)
#define _rep(i, l, r) for(int i = (l); i <= (r); i++)
#define _for(i, l, r) for(int i = (l); i < (r); i++)
#define _forDown(i, l, r) for(int i = (l); i >= r; i--)
#define debug_(ch, i) printf(#ch"[%d]: %d\n", i, ch[i])
#define debug_m(mp, p) printf(#mp"[%d]: %d\n", p->first, p->second)
#define debugS(str) cout << "dbg: " << str << endl;
#define debugArr(arr, x, y) _for(i, 0, x) { _for(j, 0, y) printf("%c", arr[i][j]); printf("\n"); }
#define _forPlus(i, l, d, r) for(int i = (l); i + d < (r); i++)

const int maxn = 100000 + 10;
int n;

class Seg {
public:
    int from, to;

    bool operator< (const Seg& rhs) const {
        if(to != rhs.to) return to < rhs.to;
        else return from < rhs.from;
    }
};

Seg seg[maxn];

int solve() {
    int ans = 0, last = -1;
    _for(i, 0, n) {
        Seg& cur = seg[i];

        if(cur.to == last) continue;
        if(cur.from <= last) {
            last++;
        }
        if(cur.from > last) {
            ans++;
            last = cur.to;
        }
    }
    return ans - 1;
}

int main() {
    freopen("input.txt", "r", stdin);
    int T;
    scanf("%d", &T);

    while (T--) {
        scanf("%d", &n);
        _for(i, 0, n) {
            scanf("%d%d", &seg[i].from, &seg[i].to);
        }

        sort(seg, seg + n);

        printf("%d\n", solve());
    }
}